1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ I've just edited with what I believed to be what you meant to write, please correct me if I'm wrong. $\endgroup$
    – David P
    Feb 25 '20 at 0:09
  • $\begingroup$ @DavidPeterson When editing, please do so thoroughly. $\endgroup$
    – amWhy
    Feb 25 '20 at 0:10
  • $\begingroup$ @Bernard You too. $\endgroup$
    – amWhy
    Feb 25 '20 at 0:12
  • $\begingroup$ I'm sorry ,I only edit what I understand. I can see there's a problem in the last sentence, but I don't know what it should really be. $\endgroup$
    – Bernard
    Feb 25 '20 at 0:14
  • $\begingroup$ @amWhy And perhaps you? Check out your subscripts in the last paragraph (which I had fixed). $\endgroup$
    – David P
    Feb 25 '20 at 0:14
2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ thank you! i'll try again $\endgroup$
    – raydiiii
    Feb 25 '20 at 0:20
  • $\begingroup$ 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. $\endgroup$
    – raydiiii
    Feb 25 '20 at 0:34
  • $\begingroup$ @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$? $\endgroup$ Feb 25 '20 at 0:38
  • $\begingroup$ omg!!! yeah I get it now!! I really don't know whats wrong with me lol. thanks a lot. $\endgroup$
    – raydiiii
    Feb 25 '20 at 0:45
  • $\begingroup$ done! hope you have a nice day. $\endgroup$
    – raydiiii
    Feb 25 '20 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.