Results 1 to 7 of 7

Math Help - Proving a recurrence

  1. #1
    Newbie
    Joined
    May 2007
    Posts
    3

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by recurrence View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2007
    Posts
    3
    Quote Originally Posted by Jhevon View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by recurrence View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member ecMathGeek's Avatar
    Joined
    Mar 2007
    Posts
    436
    Quote Originally Posted by recurrence View Post
    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)!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    May 2007
    Posts
    3
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ecMathGeek View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving an identity that's proving to be complex
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: July 21st 2009, 01:30 PM
  2. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 07:56 PM
  3. recurrence
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 8th 2009, 03:46 PM
  4. recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 1st 2009, 10:53 PM
  5. recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 7th 2008, 09:35 AM

Search Tags


/mathhelpforum @mathhelpforum