Results 1 to 5 of 5

Math Help - Recursion/induction

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    296

    Recursion/induction

    Let a0 and a1 be distinct real numbers

    Set an=(an-1+an-2)/2 for each n>=2

    Use induction to show that:

    an+1-an=(-1/2)^n*(a1-ao)

    -----------

    If we take fore n=2...a2=a1+a0/2

    And then a3=(((a1+a0)/2)+(a1))/2

    So a3-a2 should be equal to that WALBOA

    The problem I'm having is how to show that P(n)--> P(n+1)

    You can assume this is true for n, but I don't know how to show it true for n+1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Jester's Avatar
    Joined
    Dec 2008
    From
    Conway AR
    Posts
    2,347
    Thanks
    30
    Quote Originally Posted by zhupolongjoe View Post
    Let a0 and a1 be distinct real numbers

    Set an=(an-1+an-2)/2 for each n>=2

    Use induction to show that:

    an+1-an=(-1/2)^n*(a1-ao)

    -----------

    If we take fore n=2...a2=a1+a0/2

    And then a3=(((a1+a0)/2)+(a1))/2

    So a3-a2 should be equal to that WALBOA

    The problem I'm having is how to show that P(n)--> P(n+1)

    You can assume this is true for n, but I don't know how to show it true for n+1
    If a_{n+1} - a_n = \left(- \frac{1}{2}\right)^n(a_1 - a_0)

    then

     <br />
a_{n+2} - a_{n+1}<br />

     <br />
= \frac{1}{2} \left( a_{n+1} + a_n\right) - a_{n+1}<br />

     <br />
= - \frac{1}{2}\left( a_{n+1} - a_n \right)<br />

     <br />
= - \frac{1}{2} \left( - \frac{1}{2}\right)^n(a_1 - a_0)<br />

     <br />
= \left( -\frac{1}{2}\right)^{n+1}(a_1- a_0)<br />
    Last edited by Jester; October 2nd 2009 at 10:00 AM. Reason: fixed an error
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    Forgive me for my ignorance, but why do you use

    an+1-an=(-1/2)^n?

    The problem statement has a(n+1)-a(n)=(-1/2)^n*(a1-a0)

    Does (a1-a0) equal 1 here? How would we know that?

    Also, aren't you supposed to use the fact that a(n)=(a(n-1)+a(n-2))/2 in some way?

    THank you.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Jester's Avatar
    Joined
    Dec 2008
    From
    Conway AR
    Posts
    2,347
    Thanks
    30
    Quote Originally Posted by zhupolongjoe View Post
    Forgive me for my ignorance, but why do you use

    an+1-an=(-1/2)^n?

    The problem statement has a(n+1)-a(n)=(-1/2)^n*(a1-a0)

    Does (a1-a0) equal 1 here? How would we know that?

    Also, aren't you supposed to use the fact that a(n)=(a(n-1)+a(n-2))/2 in some way?

    THank you.
    I inserted the missing piece - thanks. I have used a_n = \frac{1}{2} \left(a_{n-1} + a_{n-2}\right). It's in the third line. Replace n with n+2 so a_{n+2} = \frac{1}{2} \left(a_{n+1} + a_{n}\right).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    ok, got it, thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. induction and recursion
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 25th 2009, 12:08 AM
  2. Replies: 2
    Last Post: December 4th 2008, 12:51 AM
  3. Induction and Recursion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 12th 2008, 07:59 PM
  4. Induction & Recursion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 20th 2008, 06:20 AM
  5. Induction & Recursion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 19th 2008, 11:25 AM

Search Tags


/mathhelpforum @mathhelpforum