How to prove that every third Fibonacci number is even?

  • Thread starter Eclair_de_XII
  • Start date
  • Tags Tags
    even
1 reply · 4K views · last reply
Eclair_de_XII
Messages
1,085
Reaction score
92

Homework Statement


"Consider the sequence ##F_1##, ##F_2##, ##F_3##, . . . , where
##F_1 = 1##, ##F_2 = 1##, ##F_3 = 2##, ##F_4 = 3##, ##F_5 = 5## and ##F_6 = 8##.
The terms of this sequence are called Fibonacci numbers.
(a) Define the sequence of Fibonacci numbers by means of a recurrence relation.
(b) Prove that ##2 | F_n## if and only if ##3 | n##.

Homework Equations


(a) ##F_n=F_{n-2}+F_{n-1}##

The Attempt at a Solution


(b)
Basically, I'm going to express every Fibonacci number in terms of ##mod2## and express ##n## as ##n=3x## for some ##x∈ℕ##.

For ##x=1##, ##F_3=F_1+F_2=1mod2+1mod2=0mod2##.
Then assuming that ##F_{3k}=0mod2## for some ##k>1##, I need to prove that ##F_{3(k+1)}=F_{3k+1}+F_{3k+2}##.

So I have ##F_{3k+1}=0mod2+1mod2## and ##F_{3k+2}=0mod2+1mod2##.
Adding them up gives ##F_{3(k+1)}=F_{3k+1}+F_{3k+2}=0mod2+1mod2+0mod2+1mod2=0mod2##.

And I'm pretty sure this isn't sufficient to complete the inductive proof. Can anyone check my work? Thanks.
 
You we're supposed to show iff.

The proof would be simpler if you considered the sequence in sets of 3 and explicitly showed that, modulo 2, the sequence is:

##1, 1, 0,1,1,0 \dots##