I have spent the past 7 hours trying to prove this relation

Prove that a(n) = 2^n + n! satisfies the recurrence

a(n) = 2 if n=0

a(n) = 3 if n=1

a(n) = 6 if n=2

a(n) = (n+4)a(n-1) - 4n a(n-2) + 4(n-2)a(n-3) if n>2

Printable View

- May 3rd 2007, 08:28 PMrecurrenceProving a recurrence
I have spent the past 7 hours trying to prove this relation

Prove that a(n) = 2^n + n! satisfies the recurrence

a(n) = 2 if n=0

a(n) = 3 if n=1

a(n) = 6 if n=2

a(n) = (n+4)a(n-1) - 4n a(n-2) + 4(n-2)a(n-3) if n>2 - May 3rd 2007, 09:08 PMJhevon
- May 3rd 2007, 09:11 PMrecurrence
- May 3rd 2007, 10:14 PMJhevon
Ok, this is just to get you started. I'm way too tired to continue, and i think i made a mistake somewhere in the calculations and i'm too lazy to go over it at the moment--time to sleep. anyway, here is what i have so far.

We see that a(n) = 2^n + n! holds for n = 0, 1, 2. We now show that a(n) = 2^n + n! for n > 2 by the Strong Form of Induction.

We see that this is true for n = 3 since 2^3 + 3! = (3 + 4)(6) - 4(3)(3) + 4(1)(2) = 14. Assume that a(i) = 2^i + i! holds for 3 =< i =< k, where k >= 3. We also know that a(i) holds for 1 =< i =< k. Consider a(k + 1). Since k >= 3, K + 1 >= 4, so we have

a(K + 1) = (k + 4)a(k) - 4k a(k - 1) + 4(k - 2)a(k - 2)

.........= (k + 4)(2^k + k!) - 4k (2^(k - 1) + (k - 1)!) + 4(k - 2)(2^(k - 2) + (k - 2)!)

.........= (k + 4)(2^-1 * 2^(k + 1) + k!) - 4k (2^-2 * 2^(k + 1) + (k - 1)!) + 4(k - 2)(2^-3 * 2^(k + 1) + (k - 2)!)

.........= k/2 * 2^(k + 1) + k*k! + 2*2^(k + 1) + 4*k! - k*2^(k + 1) - 4*k! + [4(k - 1) - 4](2^-3 * 2^(k + 1) + (k - 2)!)

.........= k/2 * 2^(k + 1) + k*k! + 2*2^(k + 1) - k*2^(k + 1) + (1/2)(k - 1)*2^(k + 1) - 4*(k - 1)! - 2^-1 * 2^(k + 1) - 4*(k - 2)!

.........= [k/2 + 2 - k + k/2 - 1/2 - 1/2]*2^(k + 1) + k*k! - 4*(k - 1)! - 4*(k - 2)!

.........= 2^(k + 1) + k*k! - 4*(k - 1)(k - 2)! - 4*(k - 2)!

.........= 2^(k + 1) + k*k! + (k - 2)![- 4*(k - 1) - 4]

.........= 2^(k + 1) + k*k! + (k - 2)![- 4k]

.........= 2^(k + 1) + k[k! - 4(k - 2)!]

.........= 2^(k + 1) + k[k(k - 1)(k - 2)! - 4(k - 2)!]

.........= 2^(k + 1) + k[(k - 2)!{k(k - 1) - 4}]

..............

..............

..............

we want to end up with:

.........= 2^(k + 1) + (k + 1)!

then that would prove it.

so at the moment, the challenge is to turn k[(k - 2)!{k(k - 1) - 4}] into (k + 1)! -- that is if i didn't make a mistake and it should be something else - May 3rd 2007, 10:51 PMecMathGeek
Assume n = k case:

a(k) = (k + 4)a(k - 1) - 4ka(k - 2) + 4(k - 2)a(k - 3) = 2^k + k!

Show n = k + 1 case:

a(k + 1) = (k + 5)a(k) - 4(k + 1)a(k - 1) + 4(k - 1)a(k - 2) = 2^(k + 1) + (k + 1)!

= (k + 5)(2^k + k!) - 4(k + 1)(2^(k - 1) + (k - 1)!) + 4(k - 1)(2^(k - 2) + (k - 2)!)

= k2^k + 5*2^k + k*k! + 5*k! - 4k2^(k - 1) - 4k(k - 1)! - 4*2^(k - 1) - 4(k - 1)! + 4k2^(k - 2) + 4k(k - 2)! - 4*2^(k - 2) - 4(k - 2)!

= 1/2*k2^(k + 1) + 5/2*2^(k + 1) + k*k! + 5*k! - k2^(k + 1) - 4k! - 2^(k + 1) - 4(k - 1)! + 1/2*k2^(k + 1) + 4k(k - 2)! - 1/2*2^(k + 1) - 4(k - 2)!

= 2^(k + 1)***[***1/2k + 5/2 - k - 1 + 1/2k - 1/2***]**+ (k - 2)!***[**k*k*(k - 1) + 5*k*(k - 1) - 4k(k - 1) - 4(k - 1) + 4k - 4**]**

= 2^(k + 1) + (k - 2)!*[k^3*- k^2 + 5k^2*- 5k*- 4k^2*+ 4k*- 4k + 4 + 4k**- 4*]

= 2^(k + 1) + (k - 2)!*[k^3 - k]

= 2^(k + 1) + (k - 2)!*(k)(k + 1)(k - 1)

= 2^(k + 1) + (k + 1)! - May 4th 2007, 04:19 AMrecurrence
Stupid me didn't plug in the n+1 for all n's involved in the equation. Once I saw the correct first line I was able to take off, thanks

- May 4th 2007, 05:42 AMJhevon