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

Status
Not open for further replies.

Chris L T521

Well-known member
Staff member
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$.

-----

Chris L T521

Well-known member
Staff member
This week's question was correctly answered by:

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

Here's caffeinemachine's solution:

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):

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

Status
Not open for further replies.