# Math Help - Induction

1. ## 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!

2. 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}} = ...$

3. Isn't the inductive assumption $n=k+1$? I guess how did you get
$
|x_n - x_{n-1}| = \frac{1}{2^{n-2}}
$
?

4. Originally Posted by sfspitfire23
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}$

5. Sorry fellas, I still seem lost

6. Originally Posted by sfspitfire23
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}$

7. 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}|$

8. Originally Posted by sfspitfire23
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}$

9. Originally Posted by sfspitfire23
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})
$

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?