- #1
Eclair_de_XII
- 1,083
- 91
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.