Results 1 to 9 of 9

Math Help - Induction Sequence

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    5

    Induction Sequence

    an = 1 + 2an-1
    a1 = 1
    a)Guess what an is based on inspection of this sequence
    b) Prove the expression in (a) using induction

    edit: ah my subscript got messed up, dunno how to post it on forums

    suppose to be a subscript n = 1 + 2a subscript n-1
    a subscript 1 = 1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by kentwoods View Post
    an = 1 + 2an-1
    a1 = 1
    a)Guess what an is based on inspection of this sequence
    b) Prove the expression in (a) using induction

    edit: ah my subscript got messed up, dunno how to post it on forums

    suppose to be a subscript n = 1 + 2a subscript n-1
    a subscript 1 = 1
    a_n = \{1,3,7,15,31,63,...\}

    Can you see the general pattern in the difference of every two successive elements?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    5
    yea looks like 2n + 1 ?

    How would I show this by induction tho?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by kentwoods View Post
    yea looks like 2n + 1 ?

    How would I show this by induction tho?
    How is it 2n+1?

    You have odd numbers there, yes, but the nth number is definitely not 2n+1...

    Look at it this way:

    3-1 = 2
    7-3 = 4
    15-7 = 8
    31-15 = 16

    What do 2,4,8,16 have in common?

    Or, look at it this way:

    1= 2-1
    3 = 4-1
    7 = 8-1
    15 = 16-1
    .
    .
    .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    5
    hmm

     2^n -1

    i think thats what you were trying to show me, im really bad when it comes to this

    I cannot visualize it easily
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by kentwoods View Post
    hmm

     2^n -1

    i think thats what you were trying to show me, im really bad when it comes to this

    I cannot visualize it easily
    Yes, that is correct. Now, we need to prove that a_n = 2^n -1 by induction.

    Basis: n=1: a_1 = 1, 2^1-1 = 1 = a_1 \Rightarrow correct.

    Assume that it holds for n (that is, a_n = 2^n-1), and now we need to prove that it is correct for n+1, that is, we need to prove that a_{n+1} = 2^{n+1}-1.

    a_{n+1} = 1+2a_{n} \overbrace{=}^{\text{By the assumption for n}} 1+ 2\cdot (2^n-1) = 1 + 2 \cdot 2^n - 2 = 2 \cdot 2^n - 1 = 2^{n+1}-1 \Rightarrow a_{n+1} = 2^{n+1}-1 which is what we wanted to prove, therefore the assumption holds for any n \in \mathbb{N} and we are done.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Nov 2009
    Posts
    5
    Thanks mate, that actually makes a lot of sense when i go through it slowly

    Just a quick question though, when we went over examples in class we always proved n-1 instead of n+1. Basically if one is true the one before it is true as well. I'm assuming this works the same way.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by kentwoods View Post
    Thanks mate, that actually makes a lot of sense when i go through it slowly

    Just a quick question though, when we went over examples in class we always proved n-1 instead of n+1. Basically if one is true the one before it is true as well. I'm assuming this works the same way.
    I don't think I follow. Did you assume that it is correct for n and prove for n-1? Or assume correct for n-1 and prove for n? If the latter, then that is equivalent to what I did. Otherwise, that is not the way to use induction (it is not correct).
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Nov 2009
    Posts
    5
    no I meant the latter, i meant assume for n-1 and prove for n

    thanks for your help again
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Induction on a sequence
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 2nd 2011, 10:25 AM
  2. Fibonacci Sequence - Induction Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 19th 2011, 03:41 PM
  3. induction on a reccurence sequence
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 29th 2008, 08:24 AM
  4. Induction, sequence, not hard, please help me
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 19th 2007, 11:57 AM
  5. Induction on a sequence
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 23rd 2006, 05:16 PM

Search Tags


/mathhelpforum @mathhelpforum