Results 1 to 4 of 4

Math Help - Difficult Mathematical Induction

  1. #1
    Member
    Joined
    Mar 2010
    Posts
    144

    Difficult Mathematical Induction

    a0 = 2, a1 = 3

    for any k ≥ 2 (k is a whole number)

    ak = 3ak-1 - 2ak-2

    Prove: an = 2^(n) + 1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by MATNTRNG View Post
    a0 = 2, a1 = 3

    for any k ≥ 2 (k is a whole number)

    ak = 3ak-1 - 2ak-2

    Prove: an = 2^(n) + 1
    Let's use a stronger form of induction here.


    Base case:  a_0=2=2^0+1 ,  a_1=2=2^1+1


    Yielding case: Assume  a_k = 2^k+1 and  a_{k-1} = 2^{k-1}+1 .

     a_{k+1} = 3a_k-2a_{k-1} = 3(2^k+1)-2(2^{k-1}+1) = 3\cdot2^k+3-2^k-2 = 2\cdot2^k+1 = 2^{k+1}+1


    By our use of induction, we're done.
    Last edited by chiph588@; March 28th 2010 at 03:09 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by MATNTRNG View Post
    a0 = 2, a1 = 3

    for any k ≥ 2 (k is a whole number)

    ak = 3ak-1 - 2ak-2

    Prove: an = 2^(n) + 1
    It is true for k=0,1 . Assume truth for all indexes up to k-1 and show now for k :

    a_k=3a_{k-1}-2a_{k-2}=3(2^{k-1}+1)-2(2^{k-2}+1)=3\cdot 2^{k-1}+3-2\cdot 2^{k-2}-2 <br />
=2\cdot 2^{k-1}+1=2^k+1\,\,\,\,\square

    Tonio
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Feb 2010
    From
    New Jersey, USA
    Posts
    36
    Good one!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  2. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 11th 2010, 03:17 AM
  3. Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 17th 2009, 11:30 AM
  4. mathematical induction
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 1st 2009, 07:12 AM
  5. mathematical induction
    Posted in the Algebra Forum
    Replies: 11
    Last Post: May 26th 2007, 06:54 PM

Search Tags


/mathhelpforum @mathhelpforum