Thread: Proving 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

Originally Posted by 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

have you tried induction?

Originally Posted by Jhevon

have you tried induction?

Yep. Tried 2^(n+1) + (n+1)! and only got as far as

a(n) = 2^n + n! [(n+4)-4n(2^(n-2)+(n-2)!)+(4n-8)(2^(n-3)+(n-3)!]

But can't see anywhere to go from that point

Originally Posted by 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

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

Originally Posted by 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

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)!

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

Originally Posted by ecMathGeek

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)!

oh, that's the mistake i made, i forgot to change the coefficients. thanks ecMathGeek, you will become famous soon enough