# Fibonacci number

• Feb 27th 2010, 10:46 PM
flower3
Fibonacci number
For $n \in N$ let $f_n$ be the $n^{th}$ Fibonacci number :
$f_1 = 1 \ , f_2 =1 , f_n= f_{n-1}+ f_{n-2} , n \geq 3 .$
Prove that :
$f_n \ is \ even \iff 3 \ divides \ n$
• Feb 27th 2010, 11:53 PM
chisigma
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 $f_{k}$'. In case of $k=3$ is $f_{k}=3$...

Kind regards

$\chi$ $\sigma$
• Feb 28th 2010, 12:05 AM
alexmahone
Quote:

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

Proof by induction:

Let the statement be P(n).

$f_3=1+1=2$

Thus P(3) is true.

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

Let P(m) be true.

$m=3a$

$f_m=2k$

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

Consider P(m+3).

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

Thus 3 divides m+3.

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

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

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

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

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

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

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

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