How it Works › Forums › Advanced Problems (AMC 8 Problems 20-25 and beyond) › Recursion Advanced Problems! › Reply To: Recursion Advanced Problems!

2.

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 A100-A99. 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+2A1-2A0

A4 = (A2+2A1-2A0)+2A2-2A1

Therefore, D1 = 2A2-2A1.

Interesting. Ok, let’s continue.

A4 = (A2+2A1-2A0)+2A2-2A1

A5 = (A2+2A1-2A0+2A2-2A1)+4A1-4A0

Therefore, D2 = 4A1-4A0. 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 = (3A2-2A0)+2A4-2A3

= (3A2-2A0)+2((A2+2A1-2A0)+2A2-2A1))-2(A2+2A1-2A0)

= 3A2-2A0+2A2+4A1-4A0+4A2-4A1-2A2-4A1+4A0

Simplifying like terms, we get:

7A2-4A1-2A0

= 7A2-6A1

If we subtract A5 from A6, we get:

4A2-4A1

We only care about A100-A99, which is an even – odd. 2A2-2A1 and 4A2-4A1 are the ones thtat satisfy this. We can clearly see the pattern of multiplying by 2. If we simplify for 2A2-2A1, 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^50**

**This response was written by Yash Agarwal **