Results 1 to 9 of 9

Math Help - Induction on a sequence

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    Induction on a sequence

    a_1=0, \ a_2=3, \ \ \forall n\geq 3 \ \ \ a_n=\frac{1}{2}(a_{n-1}+a_{n-2})

    Show \forall n\geq 2 \ \ \ a_n=2+4\left(-\frac{1}{2}\right)^n

    and deduce the limit is 2.

    a_2=3 \equiv 2+4\left(-\frac{1}{2}\right)^2=3

    Assume p(k) is true for a fixed but arbitrary k\geq n.

    Prove p(k+1) is true.

    I am having trouble with this piece and not sure where to start.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    First, since a_n refers to both a_{n-1} and a_{n-2}, the induction step must deduce P(n) from P(n-1) and P(n-2). I actually prefer to prove that P(k) and P(k+1) imply P(k+2) for k >= 2. Next, P(3) cannot be proved by the induction step because that would require P(1) and P(2), and we don't have P(1). Therefore, P(3) has to be proved as a part of the base case. After that, P(2) and P(3) would give P(4), P(3) and P(4) would give P(5) and so on.

    To prove the inductive step, assume P(k) and P(k+1) are true (write these statements explicitly) and use the definition of a_{k+2} to see if a_{k+2} satisfies P(k+2).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by emakarov View Post
    First, since a_n refers to both a_{n-1} and a_{n-2}, the induction step must deduce P(n) from P(n-1) and P(n-2). I actually prefer to prove that P(k) and P(k+1) imply P(k+2) for k >= 2. Next, P(3) cannot be proved by the induction step because that would require P(1) and P(2), and we don't have P(1). Therefore, P(3) has to be proved as a part of the base case. After that, P(2) and P(3) would give P(4), P(3) and P(4) would give P(5) and so on.

    To prove the inductive step, assume P(k) and P(k+1) are true (write these statements explicitly) and use the definition of a_{k+2} to see if a_{k+2} satisfies P(k+2).
    Which a_n do I use to prove this then?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    I don't understand your question. I suggest fixing an arbitrary k >= 2 (or call it n), assuming P(k) and P(k+1) and starting from the given equation for a_{k+2} to try to show that it satisfies P(k+2).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by emakarov View Post
    I don't understand your question. I suggest fixing an arbitrary k >= 2 (or call it n), assuming P(k) and P(k+1) and starting from the given equation for a_{k+2} to try to show that it satisfies P(k+2).
    I have a_n=\frac{1}{2}(a_{n-1}+a_{n-2}) or do I use

    a_n=2+4\left(-\frac{1}{2}\right)^n\text{?}
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    Quote Originally Posted by dwsmith View Post
    I have a_n=\frac{1}{2}(a_{n-1}+a_{n-2}) or do I use

    a_n=2+4\left(-\frac{1}{2}\right)^n\text{?}
    The second equality is what you have to prove for n = k + 2. The first equality is given in the definition of the sequence a_n. When working informally, one often starts with the equation one needs to prove and transforms it to a valid equation, but the final proof has to start with known equations and end with the one that has to be proved.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    By adding k and k+1, I obtain:

    a_k+a_{k+1}=2+4\left(-\frac{1}{2}\right)^k+2+4\left(-\frac{1}{2}\right)^{k+1}

    =2+2+4\left[\left(-\frac{1}{2}\right)^k+\left(-\frac{1}{2}\right)^{k+1}\right]

    Not sure where to go now though.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    The defining equation for the sequence says that not only a_k and a_{k+1} have to be added, but also the sum has to be multiplied by 1/2. Secondly, it is natural to factor out (-1/2)^k. Finally, note that (1/2)^2 = (-1/2)^2.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    =\frac{1}{2}\left(4+4\left(-\frac{1}{2}\right)^k\left[1-\frac{1}{2}\right]\right)

    2+4\left(-\frac{1}{2}\right)^{k}\left(\frac{1}{2}\right)^2

    2+4\left(-\frac{1}{2}\right)^{k}\left(-\frac{1}{2}\right)^2

    2+4\left(-\frac{1}{2}\right)^{k+2}

    Thanks for the help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Induction Sequence
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: November 5th 2009, 10:14 AM
  2. Fibonacci Sequence: Induction Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 14th 2009, 07:38 AM
  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

/mathhelpforum @mathhelpforum