Results 1 to 5 of 5

Math Help - [SOLVED] Recursive sequence induction proof

  1. #1
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599

    [SOLVED] Recursive sequence induction proof

    Define b_n as b_0 = 0 , b_1 = 3 and b_n = 7b_{n-1}-10b_{n-2}. Prove by induction that b_n=5^n-2^n

    Proof:

    Let P(n) be the propositional statement for n>1 " 5^n-2^n=7b_{n-1}-10b_{n-2}"

    The LHS of P(2) is 5^2-2^2=21 and the RHS if P(2) is 7(3)-10(0)=21. So P(2) is true.

    Now assume that P(j) is true for all j<k. That is assume 5^j-2^j=7b_{j-1}-10b_{j-2}. Then by this assumption that P(j-1) can be written as 7(5^{k-1}-2^{k-1})-10(5^{k-2}-2^{k-2})

    Now I'm kind of stuck. This is either going to take some sick algebra or I made a boo-boo.
    Last edited by Jameson; February 21st 2008 at 09:04 PM. Reason: P(x) should be P(n)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by Jameson View Post
    Define b_n as b_0 = 0 , b_1 = 3 and b_n = 7b_{n-1}-10b_{n-2}. Prove by induction that b_n=5^n-2^n

    Proof:

    Let P(x) be the propositional statement for n>1 " 5^n-2^n=7b_{n-1}-10b_{n-2}"

    The LHS of P(2) is 5^2-2^2=21 and the RHS if P(2) is 7(3)-10(0)=21. So P(2) is true.

    Now assume that P(j) is true for all j<k. That is assume 5^j-2^j=7b_{j-1}-10b_{j-2}. Then by this assumption that P(j-1) can be written as 7(5^{k-1}-2^{k-1})-10(5^{k-2}-2^{k-2})

    Now I'm kind of stuck. This is either going to take some sick algebra or I made a boo-boo.
    Under the assumption b_k = 5^k - 2^k:

    b_{k+1} = 7b_k - 10b_{k-1} = 7(5^k - 2^k) - 10(5^{k-1} - 2^{k-1})

     = 5^{k-1}(7 \times 5 - 10) - 2^{k-1}(7 \times 2 - 10) = 25 \times 5^{k-1} - 4 \times 2^{k-1} = 5^{k+1} - 2^{k+1}.

    And it's blue sky all the way ......
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    Quote Originally Posted by mr fantastic View Post
    Under the assumption b_k = 5^k - 2^k:

    b_{k+1} = 7b_k - 10b_{k-1} = 7(5^k - 2^k) - 10(5^{k-1} - 2^{k-1})

     = 5^{k-1}(7 \times 5 - 10) - 2^{k-1}(7 \times 2 - 10) = 25 \times 5^{k-1} - 4 \times 2^{k-1} = 5^{k+1} - 2^{k+1}.

    And it's blue sky all the way ......
    Very nice! Thank you Only question is about "Under the assumption b_k = 5^k - 2^k:" We assumed that P(j) for all j<k so it's safe to assume this?

    EDIT: On second thought, maybe just writing that in terms of j+1 would be better? I'm not 100% sure. I get the proof. My teacher is just a major nitpicker with tiny details.
    Last edited by Jameson; February 21st 2008 at 09:06 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by Jameson View Post
    Very nice! Thank you Only question is about "Under the assumption b_k = 5^k - 2^k:" We assumed that P(j) for all j<k so it's safe to assume this?

    EDIT: On second thought, maybe just writing that in terms of j+1 would be better? I'm not 100% sure. I get the proof. My teacher is just a major nitpicker with tiny details.
    Well, I think it's as simple as:

    Step 1: Show P(2) true. Done.

    Step 2: Assume true for n = k, that is, assume P(k) true for n = k. This is the inductive hypothesis. Done.

    Step 3: Show P(k+1) true follows from P(k) true. Done.

    Therefore, etc. etc.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    You're absolutely right. The text we have for some reason makes a case for two types of induction, the first one as you just described and the second one like this:

    "Suppose for each number, n, P(n) is a statement associated with n and the statement has the following properties:

    a)If P(k) is true whenever P(j) holds for all natural numbers j<k, then P(n) holds for all natural numbers n."

    This is essentially the same method, but for some reason when we reference the induction hypothesis we must pick one of the two. My teacher is kind of strange. But I got the proof now. Thank you very much!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Proof a recursive formula with induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 27th 2011, 02:50 PM
  2. [SOLVED] Fibonacci sequence induction proof
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 1st 2010, 10:22 AM
  3. Proof of Convergence for Recursive Sequence
    Posted in the Calculus Forum
    Replies: 9
    Last Post: June 4th 2010, 01:59 AM
  4. [SOLVED] Recursive sequence and primes
    Posted in the Number Theory Forum
    Replies: 13
    Last Post: May 12th 2010, 07:14 PM
  5. Replies: 2
    Last Post: February 5th 2009, 08:07 PM

Search Tags


/mathhelpforum @mathhelpforum