Results 1 to 9 of 9

Math Help - Induction

  1. #1
    Senior Member sfspitfire23's Avatar
    Joined
    Oct 2009
    Posts
    273

    Induction

    Hey guys, was hoping someone could walk me thru an induction proof

    Im given: x_1=1, x_2=2, x_n=\frac{1}{2}(x_{n-2}+x_{n-1}) for n>2


    Prove that |x_{n+1}-{x_n}|=\frac{1}{2^{n-1}} for all natural numbers n.

    First is base case. We see that |2-1|=1 and \frac{1}{2^{0}}=1 base case done.

    Now inductive step. Assume |x_{k+1}-{x_k}|=\frac{1}{2^{k-1}} is true.....now what do I do?

    I know how to set up a proof by induction of a sum, but these recurrence formulas just aren't clear yet.

    After this, how would I go about proving an inequality using a recurrence formula...like this problem below:

    Prove if n>m then |x_n-x_m|<\frac{1}{2^{m-2}}

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Your inductive assumption is that |x_n - x_{n-1}| = \frac{1}{2^{n-2}}.

    Now you need to prove that |x_{n+1} - x_n| = \frac{1}{2^{n-1}}. What do you get after using the sequence definition - x_n=\frac{1}{2}(x_{n-2}+x_{n-1}) for x_{n+1}?

    For the second part, use the triangle inequality to get a geometric sum:

    |x_n-x_m| \leq |x_n - x_{n-1}| + |x_{n-1} - x_m| \leq |x_n - x_{n-1}| + |x_{n-1} - x_{n-2}| + |x_{n-2} - x_m| \ ... \ \leq \sum_{i=0}^{n-m+1} |x_{n-i} - x_{n-i-1}| \overbrace{=}^{first \ q.} \ \sum_{i=0}^{n-m+1} \frac{1}{2^{n-i-2}} = ...
    Last edited by Defunkt; March 12th 2010 at 03:18 PM. Reason: Fixed indices
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member sfspitfire23's Avatar
    Joined
    Oct 2009
    Posts
    273
    Isn't the inductive assumption n=k+1? I guess how did you get
    <br />
|x_n - x_{n-1}| = \frac{1}{2^{n-2}}<br />
?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by sfspitfire23 View Post
    Hey guys, was hoping someone could walk me thru an induction proof

    Im given: x_1=1, x_2=2, x_n=\frac{1}{2}(x_{n-2}+x_{n-1}) for n>2


    Prove that |x_{n+1}-{x_n}|=\frac{1}{2^{n-1}} for all natural numbers n.

    First is base case. We see that |2-1|=1 and \frac{1}{2^{0}}=1 base case done.

    Now inductive step. Assume |x_{k+1}-{x_k}|=\frac{1}{2^{k-1}} is true.....now what do I do?

    I know how to set up a proof by induction of a sum, but these recurrence formulas just aren't clear yet.

    After this, how would I go about proving an inequality using a recurrence formula...like this problem below:

    Prove if n>m then |x_n-x_m|<\frac{1}{2^{m-2}}

    Thanks!
    Much more informative is the following exercise. If a_n=\alpha a_{n-1}+\beta a_{n-2} then a_n=C_1 \lambda _1^n+C_2 \lambda_2^n where \lambda,\lambda_2 are the real solutions (assuming there are two real solutions,but in this case there are) to x^2-\alpha x-\beta=0 and C_1,C_2 are merely the solutions to {C_1 \lambda_1+C_2 \lambda_2= a_1}\brace{C_1 \lambda_1^2+ C_2\lambda_2^2=a_2}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member sfspitfire23's Avatar
    Joined
    Oct 2009
    Posts
    273
    Sorry fellas, I still seem lost
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by sfspitfire23 View Post
    Hey guys, was hoping someone could walk me thru an induction proof

    Im given: x_1=1, x_2=2, x_n=\frac{1}{2}(x_{n-2}+x_{n-1}) for n>2


    Prove that |x_{n+1}-{x_n}|=\frac{1}{2^{n-1}} for all natural numbers n.

    First is base case. We see that |2-1|=1 and \frac{1}{2^{0}}=1 base case done.

    Now inductive step. Assume |x_{k+1}-{x_k}|=\frac{1}{2^{k-1}} is true.....now what do I do?

    I know how to set up a proof by induction of a sum, but these recurrence formulas just aren't clear yet.

    Thanks!
    x_n=\frac{1}{2}\left(x_{n-2}+x_{n-1}\right)

    If

    |x_{n+1}-x_n|=\frac{1}{2^{n-1}}

    then we need to examine if this causes

    |x_{n+2}-x_{n+1}|=\frac{1}{2^n} ?

    Proof

    x_n=\frac{1}{2}\left(x_{n-2}+x_{n-1}\right)\ \Rightarrow\ x_{n+2}=\frac{1}{2}\left(x_n+x_{n+1}\right)

    since this is the sequence itself.

    \Rightarrow\ |\frac{1}{2}x_n+\frac{1}{2}x_{n+1}-x_{n+1}|=|\frac{1}{2}x_n-\frac{1}{2}x_{n+1}|=\frac{1}{2}|x_n-x_{n+1}|=\frac{1}{2}|x_{n+1}-x_n|

    =\frac{1}{2}\ \frac{1}{2^{n-1}}=\frac{1}{2^n}
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member sfspitfire23's Avatar
    Joined
    Oct 2009
    Posts
    273
    Ah i see! Just one last Q....why could we just drop the -x_{n+1} out of the equation?

    \Rightarrow\ |\frac{1}{2}x_n+\frac{1}{2}x_{n+1}-x_{n+1}|=|\frac{1}{2}x_n-\frac{1}{2}x_{n+1}|
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by sfspitfire23 View Post
    Ah i see! Just one last Q....why could we just drop the -x_{n+1} out of the equation?

    \Rightarrow\ |\frac{1}{2}x_n+\frac{1}{2}x_{n+1}-x_{n+1}|=|\frac{1}{2}x_n-\frac{1}{2}x_{n+1}|
    \frac{1}{2}-1=\frac{-1}{2}
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Oct 2009
    Posts
    195
    Quote Originally Posted by sfspitfire23 View Post
    Hey guys, was hoping someone could walk me thru an induction proof

    Im given: x_1=1, x_2=2, x_n=\frac{1}{2}(x_{n-2}+x_{n-1}) for n>2


    Prove that |x_{n+1}-{x_n}|=\frac{1}{2^{n-1}} for all natural numbers n.

    First is base case. We see that |2-1|=1 and \frac{1}{2^{0}}=1 base case done.

    Now inductive step. Assume |x_{k+1}-{x_k}|=\frac{1}{2^{k-1}} is true.....now what do I do?

    I know how to set up a proof by induction of a sum, but these recurrence formulas just aren't clear yet.

    After this, how would I go about proving an inequality using a recurrence formula...like this problem below:

    Prove if n>m then |x_n-x_m|<\frac{1}{2^{m-2}}

    Thanks!
    We have

    |x_{n+1} - x_n| = \frac{1}{2^{n-1}} (Assume the hypothesis holds for n)

    We want to show

    |x_{n+2} - x_{n+1}| = \frac{1}{2^n} (Does the hypothesis hold for n+1?)

    Which, notice, is equivalent to saying

    |x_{n+2} - x_{n+1}| = \frac{1}{2}|x_{n+1} - x_n|

    We can decompose our x's quite easily:

    x_{n+2} = \frac{1}{2}(x_n + x_{n+1})


    x_{n+1} = \frac{1}{2}(x_{n-1} + x_n)


    x_{n} = \frac{1}{2}(x_{n-2} + x_{n-1})


    Also, note that our induction hypothesis (the first equation I listed) implies

    \frac{1}{2}(x_{n-1} + x_n - x_{n-2} - x_{n-1}) = \frac{1}{2}(x_n - x_{n-2}) = \frac{1}{2^{n-1}}

    Therefore:

    |x_{n+2} - x_{n+1}| =  \frac{1}{2}(x_n + x_{n+1} - x_{n-1} - x_n) = \frac{1}{2}(x_{n+1} - x_{n-1})<br />

    Now, substituting the values for the x_n's above, can you get this equation to look like one-half of the equation above it?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 01:36 AM
  2. Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 11th 2010, 03:08 AM
  3. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 19th 2008, 06:12 PM

Search Tags


/mathhelpforum @mathhelpforum