Problem source

The sequence $u_0$,  $u_1$, $u_2$, ... is defined by 
$$
u_0=1,\hspace{0.2in} u_1=1, \quad u_{n+1}=u_n+u_{n-1}
\hspace{0.2in}{\rm for}\hspace{0.1in}n \ge 1\,.
$$
Prove that
$$
u^2_{n+2} + u^2_{n-1} = 2( u^2_{n+1} + u^2_n ) \,.
$$
Using induction, or otherwise, prove the following result:
\[
u_{2n}  =  u^2_n + u^2_{n-1} \quad
\mbox{ and }\quad
 u_{2n+1} =  u^2_{n+1} - u^2_{n-1} 
\]
for any positive integer $n$.

Solution source

Claim: $u^2_{n+2} + u^2_{n-1} = 2( u^2_{n+1} + u^2_n )$

Proof: (By Induction).

(Base Case): $n = 1$

\begin{align*}
&& LHS &= u_{n+2}^2 + u_{n-1}^2 \\
&&&= u_3^2 + u_0^2 \\
&&&= 3^2 + 1^2 = 10\\
&& RHS &= 2(u_{n+1}^2+u_n^2) \\
&&&= 2(2^2 + 1^2) \\
&&&= 10
\end{align*}

Therefore the base case is true.

(Inductive hypothesis) Suppose $u^2_{n+2} + u^2_{n-1} = 2( u^2_{n+1} + u^2_n )$ is true for some $n = k$, ie $u^2_{k+2} + u^2_{k-1} = 2( u^2_{k+1} + u^2_k )$, the consider $n = k+1$

\begin{align*}
&& LHS &= u_{k+1+2}^2 + u_{k+1-1}^2 \\
&&&= (u_{k+1}+u_{k+2})^2+u_k^2 \\
&&&= u_{k+2}^2+u_{k+1}^2+ u_k^2 + 2u_{k+1}u_{k+2} \\
&&&= u_{k+2}^2+u_{k+1}^2+ u_k^2 + 2u_{k+1}(u_{k+1}+u_k) \\
&&&= u_{k+2}^2 + u_{k+1}^2+u_k^2+2u_{k+1}^2+2u_{k+1}u_k \\
&&&= u_{k+1}^2+2u_{k+1}^2+ u_{k+1}^2+u_k^2+2u_{k+1}u_k \\
&&&= u_{k+2}^2+2u_{k+1}^2+ (u_{k+1}+u_k)^2 \\
&&&= u_{k+2}^2+2u_{k+1}^2+ u_{k+2}^2 \\
&&&=2(u_{k+2}^2+u_{k+1}^2) \\
&&&= RHS
\end{align*}

Therefore it is true for $n = k+1$.

Therefore by the principle of mathematical induction it is true for all $n \geq 1$


Claim: $ u_{2n}  =  u^2_n + u^2_{n-1} \quad
\mbox{ and }\quad u_{2n+1} =  u^2_{n+1} - u^2_{n-1} $

Proof: Notice that $\begin{pmatrix}u_{n+1} \\ u_n \end{pmatrix}= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix}1 \\1 \end{pmatrix}$, in particular \begin{align*}
&& \begin{pmatrix}u_{n}& u_{n-1} \\ u_{n-1} & u_{n-2}  \end{pmatrix}&= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n} \\
\Rightarrow && \begin{pmatrix}u_{2n}& u_{2n-1} \\ u_{2n-1} & u_{2n-2}  \end{pmatrix}&= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{2n} \\
&&&= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n}  \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n} \\
&&&=\begin{pmatrix}u_{n}& u_{n-1} \\ u_{n-1} & u_{n-2}  \end{pmatrix}\begin{pmatrix}u_{n}& u_{n-1} \\ u_{n-1} & u_{n-2}  \end{pmatrix}\\
&&&= \begin{pmatrix}u_{n}^2+u_{n-1}^2& u_{n-1}(u_n+u_{n-2}) \\  u_{n-1}(u_n+u_{n-2}) & u_{n-1}^2+u_{n-2}^2  \end{pmatrix}
\end{align*}

Therefore $u_{2n} = u_{n}^2+u_{n-1}^2$ and $u_{2n+1} = u_n(u_{n+1}+u_{n-1}) =(u_{n+1}-u_{n-1})(u_{n+1}-u_{n-1}) = u_{n+1}^2-u_{n-1}^2$