2
$\begingroup$

For Fibonacci Sequence, We know that the recursive difference equation is:

$$ x_{n+2} = x_n + x_{n+1}\ \ \ \ n\ \geq 0 $$

And that the closed form solution is:

$$ x_n = \frac{1}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^{n} - \left(\frac{1-\sqrt{5}}{2}\right)^{n} \right]\ \ \ \ n \geq 0 $$

But how to prove that this fibonacci property is true using this information?:

$$x^2_n + x^2_{n+1}=x_{2n+1}$$

Hint: substitute the closed form expression for the fibonacci sequence into difference equation and verify that its true.

well...I've tried this at least 3 different ways of doing exactly as hinted without much luck...the equation always blows up on me. Any ideas how to prove it?

$\endgroup$
  • 1
    $\begingroup$ Can you show one or more of those 3 different ways? It is hard to guess at what you're doing wrong when we don't know what you're doing. $\endgroup$ – Henning Makholm Jan 7 at 23:43
  • $\begingroup$ Hint: with $x_0=0,x_1=1$, prove by induction over $m$ that $x_p=x_{m+1}x_{p-m}+x_mx_{p-m-1}$. $\endgroup$ – Mindlack Jan 8 at 0:06
7
$\begingroup$

The 'standard proof' uses strong induction, and I'll leave you to figure that out.

Let $\varphi$ and $\psi$ represent the two roots of $x^2-x-1=0$ where $\varphi > \psi$ (i.e. $\varphi,\psi=\frac{1\pm \sqrt{5}}{2}$). The given closed form solution is $$F_n=\frac{\varphi ^n-\psi ^n}{\sqrt{5}}$$ so we know $$F_n^2=\frac{\varphi ^{2n}-2(\varphi \psi)^n+\psi ^{2n} }{5}$$ and $$F_{n+1}^2=\frac{\varphi ^{2n+2}-2(\varphi \psi )^{n+1}+\psi ^{2n+2}}{5}$$ so $$F_n^2+F_{n+1}^2=\frac{\varphi ^{2n}-2(\varphi \psi)^n+\psi ^{2n}+\varphi ^{2n+2}-2(\varphi \psi )^{n+1}+\psi ^{2n+2} }{5}$$But we know that $\varphi \psi =-1$, so either $(\varphi\psi)^n=1$ and $(\varphi\psi)^{n+1}=-1$ or $(\varphi\psi)^n=-1$ and $\varphi\psi)^{n+1}=1$. Either way, the two terms cancel each other, so$$F_n^2+F_{n+1}^2=\frac{\varphi^{2n}(1+\varphi ^2)+\psi ^{2n}(1+\psi^2)}{5}$$It can be easily seen that $\frac{1+\varphi^2}{\sqrt{5}}=\varphi$ and $\frac{1+\psi^2}{\sqrt{5}}=-\psi$ so the above becomes \begin{align*}F_n^2+F_{n+1}^2&=\frac{\varphi^{2n}(1+\varphi ^2)+\psi ^{2n}(1+\psi^2)}{5}\\ &=\frac{\varphi^{2n}\cdot \varphi\sqrt{5} + \psi^{2n}\cdot (-\psi\sqrt{5})}{5} \\ &=\frac{\sqrt{5}(\varphi^{2n+1}-\psi^{2n+1})}{5} \\ &=\frac{\varphi^{2n+1}-\psi^{2n+1}}{\sqrt{5}} \\ &= F_{2n+1}\end{align*}completing the proof.

$\endgroup$
  • 1
    $\begingroup$ This seems to be the approach being hinted at. From OP's perspective, I think the insight that was missing was that we should expand things in terms of $\varphi$ and $\psi$, rather than in the way one typically "expands and simplifies". $\endgroup$ – Omnomnomnom Jan 8 at 0:10
7
$\begingroup$

For what it's worth, there's a nice approach using matrices. We can characterize the recurrence by $$ \pmatrix{x_{n+1}\\x_n} = \pmatrix{1&1\\1&0}\pmatrix{x_{n}\\x_{n-1}}, \quad n \geq 1 $$ Let $F = \pmatrix{1&1\\1&0}$. As a consequence of this characterization, we end up with the formula $$ F^n = \pmatrix{x_{n+1} & x_n\\ x_n & x_{n-1}} $$ We now compute $$ (F^n)^2 = \pmatrix{x_{n+1} & x_n\\ x_n & x_{n-1}}^2 = \pmatrix{x_{n+1}^2 + x_n^2 & x_{n+1}x_n + x_n x_{n-1}\\ x_{n+1}x_n + x_n x_{n-1} & x_n^2 + x_{n-1}^2} $$ On the other hand, $$ (F^n)^2 = F^{2n} = \pmatrix{x_{2n+1} & x_{2n}\\ x_{2n} & x_{2n-1}} $$ Because the two matrices are equal, their upper-left entries are equal, which is exactly the desired conclusion.

$\endgroup$
0
$\begingroup$

$x_{2n+1}=x_{2n}+x_{2n-1}=x_2x_{2n}+x_1x_{2n-1}=x_2(x_{2n-1}+x_{2n-2})+x_1x_{2n-1}=(x_1+x_2)x_{2n-1}+x_2x_{2n-2}=x_3x_{2n-1}+x_2x_{2n-2}=x_4x_{2n-2}+x_3x_{2n-3}=\cdots =x_xx_n+x_{n+1}x_{n+1}=x_n^2+x_{n+1}^2.$

$\endgroup$
-3
$\begingroup$

Based on the title of the topic and the hint, you need to plug the Closed form expression into your equality

$$x_{n}^2+x_{n+1}^2-x_{2n+1}$$

and make sure it equals zero identically.

Best way is to taky any CAS and plug the figures. For Wolfram Mathematica

x[n_] := 1/Sqrt[5]*(((1 + Sqrt[5])/2)^n - ((1 - Sqrt[5])/2)^n);

x[a]^2 + x[a + 1]^2 - x[2*a + 1]

Simplify[Out[]]

Then you get something like this

$$\frac{1}{5} \left(\left(\frac{2}{\sqrt{5}+1}\right)^{-a-1}-\left(\frac{1}{2} \left(1-\sqrt{5}\right)\right)^{a+1}\right)^2+\frac{1}{5} \left(\left(\frac{1}{2} \left(\sqrt{5}+1\right)\right)^a-\left(\frac{1}{2} \left(1-\sqrt{5}\right)\right)^a\right)^2-\frac{\left(\frac{2}{\sqrt{5}+1}\right)^{-2 a-1}-\left(\frac{1}{2} \left(1-\sqrt{5}\right)\right)^{2 a+1}}{\sqrt{5}}$$

You need to carefully open up all brackets, cancel out the terms to get zero.

$\endgroup$

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.