1. ## Fibonacci number

For $\displaystyle n \in N$ let $\displaystyle f_n$ be the $\displaystyle n^{th}$ Fibonacci number :
$\displaystyle f_1 = 1 \ , f_2 =1 , f_n= f_{n-1}+ f_{n-2} , n \geq 3 .$
Prove that :
$\displaystyle f_n \ is \ even \iff 3 \ divides \ n$

2. According to...

Fibonacci number - Wikipedia, the free encyclopedia

... a basic property of the fibonacci's numbers is that 'every 3rd number of the sequence is even and more generally, every k-th number of the sequence is a multiple of $\displaystyle f_{k}$'. In case of $\displaystyle k=3$ is $\displaystyle f_{k}=3$...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$

3. Originally Posted by flower3
For $\displaystyle n \in N$ let $\displaystyle f_n$ be the $\displaystyle n^{th}$ Fibonacci number :
$\displaystyle f_1 = 1 \ , f_2 =1 , f_n= f_{n-1}+ f_{n-2} , n \geq 3 .$
Prove that :
$\displaystyle f_n \ is \ even \iff 3 \ divides \ n$
Proof by induction:

Let the statement be P(n).

$\displaystyle f_3=1+1=2$

Thus P(3) is true.

--------------------------------------------------

Let P(m) be true.

$\displaystyle m=3a$

$\displaystyle f_m=2k$

--------------------------------------------------

Consider P(m+3).

$\displaystyle m+3=3a+3=3(a+3)$

Thus 3 divides m+3.

$\displaystyle f_{m+3}=f_{m+2}+f_{m+1}$

$\displaystyle f_{m+3}=f_{m+1}+f_m+f_{m+1}$

$\displaystyle f_{m+3}=2f_{m+1}+f_m$

$\displaystyle f_{m+3}=2f_{m+1}+2k$

$\displaystyle f_{m+3}=2(f_{m+1}+k)$

Thus $\displaystyle f_{m+3}$ is even.

--------------------------------------------------

Hence, by the principle of induction, the statement is true.