Chapter 12.5, Problem 29E

To determine

To Prove: $F_{3n}$ for all natural numbers $n$ .

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

  $F_{3n}$ is even for all natural numbers $n$

Put $n=1$

We get

  $\begin{array}{l}{F}_{3n}=F_{3\left(1\right)}\\ \Rightarrow F_{3n}=F_3\\ \Rightarrow F_{3n}=F_2+F_1\\ \Rightarrow F_{3n}=1+1\\ \Rightarrow F_{3n}=2\end{array}$

2 is even.

So

It True for $n=1$ .

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

So

  $F_{3k}$ is even number is True.

Therefore

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

  $\begin{array}{l}{F}_{3n}=F_{3\left(k+1\right)}\\ \Rightarrow F_{3n}=F_{3k+3}\\ \Rightarrow F_{3n}=F_{3k+2}+F_{3k+1}\\ \Rightarrow F_{3n}=F_{3k+1}+F_{3k}+F_{3k+1}\\ \Rightarrow F_{3n}=2F_{3k+1}+F_{3k}\end{array}$

As $F_{3k}$ is even number and $2F_{3k+1}$ is a multiple of 2

So, $2F_{3k+1}$ is also even number

So, Sum of both of them will be even number.

Therefore

  $F_{3n}$ is True for $n=k+1$ .

And hence the proof by Mathematical induction.