Results 1 to 3 of 3

Math Help - Proof: Recursion Equality

  1. #1
    ARD
    ARD is offline
    Newbie
    Joined
    Feb 2009
    Posts
    3

    Proof: Recursion Equality

    Proofs, doncha love 'um? ... Well, I guess some of you might...
    Anyway, down to business.

    Define the function Q(n), (n is a Positive Integer) by
    Q(0)=2,
    Q(1)=6,
    Q(x)=6Q(x-1)-5Q(x-2)
    Prove by Induction Q(n) = (5^n)+1


    I admit, I can't do proofs well to begin with. I can usually blunder through induction; but I don't know how to write it when it uses recursion without doing an ever-expanding blob of variables and equations that all look the same.

    Any assistance you could provide would be very appreciated.

    I should note that I do understand what is going on... it just gives me a headache to try and prove it >.<
    Last edited by ARD; February 17th 2009 at 08:07 AM. Reason: Clarification
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    First show that Q(2)=5^2+1.
    Assume Q(K) is true for K>2.
    Then Q(K+1)=6Q(K)-5Q(K-1)=6\left[5^K + 1\right]-5\left[5^{K-1} + 1\right].
    Now show that is equal to 5^{K+1} + 1.

    Your instructor may insist that 'strong induction' should be used.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    ARD
    ARD is offline
    Newbie
    Joined
    Feb 2009
    Posts
    3
    Eureka!

    That's what I needed, the rest is just fancy numbers...

    6(5^n+1)-5((5^(n-1))+1)=
    6(5^n)+6-5(5^(n-1))-5
    6(5^n)-(5^n)+1
    5(5^n)+1
    (5^n+1)+1

    Thus 6((5^n)+1)-5((5^(n-1))+1)=(5^n+1)+1
    Proving Q(n+1)

    Thank you!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. equality proof
    Posted in the Calculus Forum
    Replies: 5
    Last Post: March 26th 2011, 11:00 PM
  2. Replies: 2
    Last Post: September 29th 2009, 12:44 PM
  3. Root 2 recursion proof help
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 27th 2009, 02:31 AM
  4. Recursion Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 24th 2008, 12:11 PM
  5. Equality proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 8th 2006, 02:21 AM

Search Tags


/mathhelpforum @mathhelpforum