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!