GATE CSE 1996 | Question: 9

Question

The Fibonacci sequence $\{f_1, f_2, f_3 \ldots f_n\}$ is defined by the following recurrence:$$f_{n+2} = f_{n+1} + f_n, n \geq 1; f_2 =1:f_1=1$$Prove by induction that every third element of the sequence is even.

Answer 1

Formal proof,$$f_{n+2}=f_{n+1}+f_{n}$$For $n=1,$
$f_{3}=f_{2}+f_{1} = 1 + 1 = 2$ is an even number

and $f_{3},$ here $3\%3=0$

Hence, the statement is true for $n=1$

Now, let this statement is true for $n=k$

So, $f_{k+2}=f_{k+1}+f_{k},$ where $f_k$ and $f_{k+1}$ is $\text{ODD}$ and $f_{k+2}$ is $\text{EVEN},$ and also $(k+2)\%3=0$

Now, Prove this statement true for $(k+5)$ which is next to $3^{rd}$ number after $(k+2)$

$f_{k+3}=f_{k+2}+f_{k+1} = \text{ODD}(\text{EVEN} + \text{ODD})$

$f_{k+4}=f_{k+3}+f_{k+2}= \text{ODD}(\text{ODD} + \text{EVEN})$

$f_{k+5}=f_{k+4}+f_{k+3}= \text{EVEN}(\text{ODD} + \text{ODD})$

Hence, it is also true for $(k+5).$

So$,$ By the principle of mathematical induction $f(n), $ is true for all $n\%3=0$