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

1. 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^{n-2} + d*(-e)^{n-2} 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^(n-1) + 2c*k^(n-2) -2c*k^(n-3). Divide both sides by c*k^(n-3) to get:

k^3 = k^2 + 2k -2

k^2(k-1) + 2(k-1) = 0

k = 1

A_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 = 1

I 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:143

It 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_{k-1} + F_{k}

S_{k-1} = S_{k-2} + F_{k-1}

S_{k} = S_{k-1} + F{k-1} + F_{k}

However, F_{k-1} + F_{k} = F{k+1}, so we can replace it into our equation.

S_{k} = S_{k-2} + F{k+1}

I’m got stuck here