How it Works › Forums › Advanced Problems (AMC 8 Problems 2025 and beyond) › Recursion Advanced Problems!
This topic contains 5 replies, has 2 voices, and was last updated by Neha 3 months, 4 weeks ago.

AuthorPosts

MathJax TeX Test Page
Hey Math Circle Students!Here are the advanced problems for the next $3$ days! These are more difficult than the introductory problems and ask you to think critically. Each of these problems are worth $10$ points for your leaderboard score!
If you don’t understand one of the questions, feel free to post in the questions forum here
1. Let $A_n=2A_{n2}$ where $A_0=1$ and $A_1=3$. Find a closed form (simple formula in terms of $n$) for $A_n$.
2. Define a recursion $A_n = A_{n−1} + 2A_{n−2} − 2A_{n−3}$ where $A_0 = A_1 = 1$ and $A_2 = 3$. Find $A_{100}A_{99}$.
3. Refer to the introductory problem #2 or problem #4 on this week’s handout. If we let $F_n$ be the $n$th Fibonacci Number where $F_1=1$ and $F_2=1$, then what is $F_1+F_2+…+F_k$. Try it for $k=1,2,3,4,5…$ and find a pattern. Try to prove it if you can. (If you can’t find a pattern, then just write out your answers for $k=1,2,3,4,5,6,7,8,9,10$.
Remember that you can post your solutions below to these problems and I will keep a running leaderboards for the top 10 students who participate the most! I especially appreciate the same problem being solved in different ways!
Anton1. First, list a few terms:1, 3, 2, 6, 4, 12, 8, 24
This most likely is an exponential function with base 2, and we can see that the differences between an even term and odd term are powers of two, so it is probably of the form
c*2^(n) = c*2^{n2} + d*(e)^{n2} for some constants c, d, and e.I’m not too sure if what I have so far is correct, or how to continue
2.c*k^(n) = c*k^(n1) + 2c*k^(n2) 2c*k^(n3). Divide both sides by c*k^(n3) to get:
k^3 = k^2 + 2k 2
k^2(k1) + 2(k1) = 0
k = 1A_n = c*1^(n) + d(1)^n
We plug in n=1 and n=2:
A_1 = 1 = c d
A_2 = 3 = c + d
c = 2, d = 1I ended up getting A_n = 2 + (1)^n, but this obviously isn’t right. Where did I go wrong?
3.
k=1:1
k=2:2
k=3:4
k=4:7
k=5:12
k=6:20
k=7:33
k=8:54
k=9:88
k=10:143It seems like when k=n, the sum is F_{k+2}1
We can let the recurrence S_k be the sum of the Fibonacci numbers up to k
We can prove this with induction.
First, we have the base case S_1 = 1.
Then, we need to prove that if it works for S_k, then it works for S_k+1
S_{k} = S_{k1} + F_{k}
S_{k1} = S_{k2} + F_{k1}
S_{k} = S_{k1} + F{k1} + F_{k}
However, F_{k1} + F_{k} = F{k+1}, so we can replace it into our equation.
S_{k} = S_{k2} + F{k+1}I’m got stuck here
Yash Agarwal2.
We can list a few terms:
1, 1, 3, 3, 7, 7…
But this doesn’t help us. To solve this problem, we don’t need to find out A100 or A99. We just need to find out A100A99. So, we take another set of numbers D of n, which is the set of differences. And, we will put these terms in terms of A0, A1, or A2. So, let us begin:
A3 = A2+2A12A0
A4 = (A2+2A12A0)+2A22A1Therefore, D1 = 2A22A1.
Interesting. Ok, let’s continue.
A4 = (A2+2A12A0)+2A22A1
A5 = (A2+2A12A0+2A22A1)+4A14A0Therefore, D2 = 4A14A0. Since A6 is a teeny bit too large to write it all out, I will simplify A5. Please note that I will deem A1 and A0 as equal since they are given as equal in the problem.
A6 = (3A22A0)+2A42A3
= (3A22A0)+2((A2+2A12A0)+2A22A1))2(A2+2A12A0)
= 3A22A0+2A2+4A14A0+4A24A12A24A1+4A0
Simplifying like terms, we get:7A24A12A0
= 7A26A1If we subtract A5 from A6, we get:
4A24A1
We only care about A100A99, which is an even – odd. 2A22A1 and 4A24A1 are the ones thtat satisfy this. We can clearly see the pattern of multiplying by 2. If we simplify for 2A22A1, we get 4. We keep on doubling, and then we see a pattern. We can write D of n in closed form:
D(n) = 2^(n/2)
4, 8, 16…
So, if n = 100, the answer we plug 100 in for n and get:
D(100) = 2 ^ (100/2)
= 2^50This response was written by Yash Agarwal
Ayush AgarwalGreat Job Yash! You have received 10 points for your second solution. Excellent work
ShriyaI noticed something interesting: 1+1+2+3+5+7=19, which is also a Fibonnaci number! I don’t know how to prove this though.
NehaHey Shriya,
I think you can do induction like Ayush said in class. So:
F_0+F_1+..++F_{n+1} = (F_0+..+F_n)+F_{n+1}
That is how you can do the inductive step.

AuthorPosts