1. ## Induction

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

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

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

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

Now inductive step. Assume $\displaystyle |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 $\displaystyle n>m$ then $\displaystyle |x_n-x_m|<\frac{1}{2^{m-2}}$

Thanks!

2. Your inductive assumption is that $\displaystyle |x_n - x_{n-1}| = \frac{1}{2^{n-2}}$.

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

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

$\displaystyle |x_n-x_m| \leq |x_n - x_{n-1}| + |x_{n-1} - x_m| \leq$ $\displaystyle |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}|$ $\displaystyle \overbrace{=}^{first \ q.} \ \sum_{i=0}^{n-m+1} \frac{1}{2^{n-i-2}} = ...$

3. Isn't the inductive assumption $\displaystyle n=k+1$? I guess how did you get
$\displaystyle |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: $\displaystyle x_1=1, x_2=2, x_n=\frac{1}{2}(x_{n-2}+x_{n-1})$ for $\displaystyle n>2$

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

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

Now inductive step. Assume $\displaystyle |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 $\displaystyle n>m$ then $\displaystyle |x_n-x_m|<\frac{1}{2^{m-2}}$

Thanks!
Much more informative is the following exercise. If $\displaystyle a_n=\alpha a_{n-1}+\beta a_{n-2}$ then $\displaystyle a_n=C_1 \lambda _1^n+C_2 \lambda_2^n$ where $\displaystyle \lambda,\lambda_2$ are the real solutions (assuming there are two real solutions,but in this case there are) to $\displaystyle x^2-\alpha x-\beta=0$ and $\displaystyle C_1,C_2$ are merely the solutions to $\displaystyle {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: $\displaystyle x_1=1, x_2=2, x_n=\frac{1}{2}(x_{n-2}+x_{n-1})$ for $\displaystyle n>2$

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

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

Now inductive step. Assume $\displaystyle |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!
$\displaystyle x_n=\frac{1}{2}\left(x_{n-2}+x_{n-1}\right)$

If

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

then we need to examine if this causes

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

Proof

$\displaystyle 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.

$\displaystyle \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|$

$\displaystyle =\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 $\displaystyle -x_{n+1}$ out of the equation?

$\displaystyle \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 $\displaystyle -x_{n+1}$ out of the equation?

$\displaystyle \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}|$
$\displaystyle \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: $\displaystyle x_1=1, x_2=2, x_n=\frac{1}{2}(x_{n-2}+x_{n-1})$ for $\displaystyle n>2$

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

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

Now inductive step. Assume $\displaystyle |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 $\displaystyle n>m$ then $\displaystyle |x_n-x_m|<\frac{1}{2^{m-2}}$

Thanks!
We have

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

We want to show

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

Which, notice, is equivalent to saying

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

We can decompose our x's quite easily:

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

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

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

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

$\displaystyle \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:

$\displaystyle |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 $\displaystyle x_n$'s above, can you get this equation to look like one-half of the equation above it?