Problem of the Week #39 - December 24th, 2012

[Chris L T521]

Thanks to those who participated in last week's POTW!! Here's this week's problem!

-----

Problem: One defines the Fibonacci sequence by $F_1=1,\,F_2=1,\,F_{n+2}=F_n+F_{n+1}$ for $n\geq 1$. Show that for all $n\in\mathbb{N}$, $F_{n+1}^2-F_nF_{n+2}=(-1)^n$.

-----

Remember to read the POTW submission guidelines to find out how to submit your answers!

 

[Chris L T521]

This week's question was correctly answered by:

- caffeinemachine,
- Deveno,
- MarkFL,
- melese,
- Opalg, and
- Sudharaka

Here's caffeinemachine's solution:

Spoiler

Let $P(n)$ denote the statement $F_n^2-F_{n-1}F_{n+1}=(-1)^n$. When $P(n)$ is true we write $P(n)=1$. $P(1),P(2)=1$ can be verified by computation. We assume that $P(1),\ldots,P(n)=1$, where $n\geq 2$. Now we try to establish $P(n+1)=1$.
\begin{align*}
F_{n+1}^2-F_nF_{n+2}&=(F_{n}+F_{n-1})^2-F_nF_{n+2}\\
&=F_n^2+F_{n-1}^2+2F_nF_{n-1}-F_nF_{n+2}\\
&=F_n^2+F_{n-1}^2+2F_nF_{n-1}-F_n(F_{n+1}+F_{n})\\
&=F_n^2+F_{n-1}^2+2F_nF_{n-1}-F_nF_{n+1}-F_{n}^2\\
&=F_{n-1}^2+2F_nF_{n-1}-F_nF_{n+1}\\
&=(-1)^{n-1}+F_{n-2}F_n+2F_nF_{n-1}-F_nF_{n+1}\,\,\,\,(\text{by using P(n-1)=1})\\
&=(-1)^{n-1}+F_{n}(F_{n-2}+F_{n-1})+F_nF_{n-1}-F_nF_{n+1}\\
&=(-1)^{n_1}+F_n^2-F_n(F_{n+1}-F_{n-1})\\
&=(-1)^{n-1}+F_n^2-F_n(F_n)\\
&=(-1)^{n-1}\\
&=(-1)^{n+1}
\end{align*}

This establishes $P(n+1)=1$. By principle of mathematical induction the proof is complete.

Here's Sudharaka's solution (for something different than induction):

Spoiler

Let \(F_n=r^n\) as the trial solution and we get the characteristic equation,\[r^2-r-1=0\Rightarrow r=\frac{1\pm\sqrt{5}}{2}\]
Therefore the general solution is,
\[F_n=A\left(\frac{1+\sqrt{5}}{2}\right)^n+B\left( \frac{1-\sqrt{5}}{2}\right)^n~;~n\in\mathbb{Z}^+\]
where \(A\) and \(B\) are arbitrary constants. Since \(F_1=1\) and \(F_2=1\) we have,
\[A=\frac{1}{\sqrt{5}},B=-\frac{1}{\sqrt{5}}\]
\[\therefore F_n=\frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}} \left( \frac{1-\sqrt{5}}{2}\right)^n~;~n\in\mathbb{Z}^+\]
Now consider \(F^{2}_{n+1}-F_n F_{n+2}\)
\begin{eqnarray}
F^{2}_{n+1}-F_n F_{n+2}&=&F^{2}_{n+1}-F_n(F_n+F_{n+1})\\
&=&\left(F_{n+1}-\left(\frac{1+\sqrt{5}}{2}\right)F_n\right)\left(F_{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)F_n\right)
\end{eqnarray}
Substituting \(F_n=\frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}} \left( \frac{1-\sqrt{5}}{2}\right)^n\) we get,
\[\begin{aligned}&\phantom{=} F^{2}_{n+1}-F_n F_{n+2}\\ &=\left(-\frac{1}{\sqrt{5}} \left( \frac{1-\sqrt{5}}{2}\right)^{n+1}+\frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2}\right) \left( \frac{1-\sqrt{5}}{2}\right)^n\right)\left(\frac{1}{\sqrt{5}} \left( \frac{1+\sqrt{5}}{2}\right)^{n+1}-\frac{1}{\sqrt{5}}\left( \frac{1-\sqrt{5}}{2}\right) \left( \frac{1+\sqrt{5}}{2}\right)^n\right)\end{aligned}\]
\[F^{2}_{n+1}-F_n F_{n+2}= \frac{1}{5} (-1)^{n}\left(-\left( \frac{1-\sqrt{5}}{2}\right)+\left(\frac{1+\sqrt{5}}{2} \right) \right) \left(\left(\frac{1+\sqrt{5}}{2} \right)-\left(\frac{1-\sqrt{5}}{2} \right) \right)\]
\[\therefore F^{2}_{n+1}-F_n F_{n+2}= (-1)^n\mbox{ where }n\in\mathbb{Z}^+\]