Chapter 12.5, Problem 33E

To determine

To Prove: ${\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n=\left[\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right]$ for $n\ge 2$ .

Explanation of Solution

Given information:

Use Mathematical induction to prove the above mentioned formula.

  $\begin{array}{l}{F}_1=1\\ F_2=1\\ F_n=F_{n-1}+F_{n-2}\end{array}$ .

Concept used:

1.By using Mathematical induction technique we need to prove that this formula holds True for all natural numbers. The first step is to prove True for $n=1$ .

2.Second step by using induction hypothesis of mathematical induction we assume for $n=k$ given formula is True.

3.Third step is we need to prove that above formula is True for $n=k+1$ by using formula is True for $n=k$ .

Proof:

First, we need to prove the above formula is True for $n=1$ .

Given formula is

  $\begin{array}{l}{\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n=\left[\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right]\\ \end{array}$

Put $n=1$

We get

Left hand side = ${\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^1=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$

Right hand side = $\left[\begin{array}{cc}{F}_{1+1}& F_1\\ F_1& F_{1-1}\end{array}\right]=\left[\begin{array}{cc}{F}_2& F_1\\ F_1& F_0\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$

So

Left hand side = Right hand side

It True for $n=1$ .

Let us assume it is True for $n=k$

So

  ${\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^k=\left[\begin{array}{cc}{F}_{k+1}& F_k\\ F_k& F_{k-1}\end{array}\right]$ is True.

Therefore

We need to prove it is True for $n=k+1$

Left hand side = ${\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^{k+1}$

  $\Rightarrow$ Left hand side = ${\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^k\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$

  $\Rightarrow$ Left hand side = $\left[\begin{array}{cc}{F}_{k+1}& F_k\\ F_k& F_{k-1}\end{array}\right]\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$

  $\Rightarrow$ Left hand side = $\left[\begin{array}{cc}{F}_{k+1}+F_k& F_{k+1}+0\cdot F_k\\ F_k+F_{k-1}& F_k+0\cdot F_{k-1}\end{array}\right]$

  $\Rightarrow$ Left hand side = $\left[\begin{array}{cc}{F}_{k+1}+F_k& F_{k+1}\\ F_k+F_{k-1}& F_k\end{array}\right]$

  $\Rightarrow$ Left hand side = $\left[\begin{array}{cc}{F}_{k+2}& F_{k+1}\\ F_{k+1}& F_k\end{array}\right]$

Right hand side = $\left[\begin{array}{cc}{F}_{k+1+1}& F_{k+1}\\ F_{k+1}& F_{k+1-1}\end{array}\right]$

  $\Rightarrow$ Right hand side = $\left[\begin{array}{cc}{F}_{k+2}& F_{k+1}\\ F_{k+1}& F_k\end{array}\right]$

Left hand side =Right hand side

Therefore

  ${\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n=\left[\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right]$ is True for $n=k+1$ .

And hence the proof by Mathematical induction.