1

I'm trying to prove the following by induction but I'm stuck.

$x_1 = 1, x_2 = 2, x_n=\frac{1}{2}(x_{n-1}+x_{n-2})$.

Show that: $x_n-x_{n+1} = \frac{(-1)^n}{2^{n-1}}$

I proved the basis step, but I'm stuck in the inductive step. I tried going from L.H.S and take as $x_{n+2}$ as common divisor and had $(x_{n-1} - 1)$. I didn't know where to go from there..

bjorn93
  • 6,787
raydiiii
  • 83

1 Answers1

2

Hint:

Note you have, using the recurrence relation,

$$\begin{equation}\begin{aligned} x_{n+1} - x_{n+2} & = x_{n+1} - \frac{1}{2}(x_{n+1} + x_{n}) \\ & = x_{n+1} - \frac{x_{n+1}}{2} - \frac{x_{n}}{2} \\ & = \frac{1}{2}(x_{n+1} - x_{n}) \\ & = -\frac{1}{2}(x_{n} - x_{n+1}) \end{aligned}\end{equation}\tag{1}\label{eq1A}$$

John Omielan
  • 47,976
  • I tried doing that. i've substituted $x_n$ value but I'm not sure what to cancel with $x_{n+1}$ I feel so dumb because it seems so simple. thanks in advance. – raydiiii Feb 25 '20 at 00:34
  • @raydiiii I'm not sure what you mean by "not sure what to cancel with $x_{n+1}$". Note in my ($1$) equation, if you substitute for $x_n - x_{n+1}$ what you have by the assumption in the inductive step, i.e., that $x_n - x_{n+1} = \frac{(-1)^n}{2^{n-1}}$, you'll get that $x_{n+1} - x_{n+2} = -\frac{1}{2}\left(\frac{(-1)^n}{2^{n-1}}\right) = \frac{(-1)^{n+1}}{2^{n}} = \frac{(-1)^{n + 1}}{2^{(n+1)-1}}$. Do you see this is in the same form as your assumption, but with $n$ replaced with $n + 1$? – John Omielan Feb 25 '20 at 00:38
  • omg!!! yeah I get it now!! I really don't know whats wrong with me lol. thanks a lot. – raydiiii Feb 25 '20 at 00:45
  • done! hope you have a nice day. – raydiiii Feb 25 '20 at 00:49