Suppose that F1 = F2 = 1 and that
Fn = Fn-2 + Fn-1,
For all natural number n >= 3, This sequence is called the Fibonacci sequence. Show
that if 3 divides n, then 2 divides Fn. You may use any suitable proof technique.
My Answer :
I use strong induction to proof
Proof :
A. Base n=3
F3 = F2 + F1
F3 = 1 + 1 = 2, so, the statement is true for the base
B. Induction hypothesis
3 divides n. Therefore, n can be expressed: n = 3k, for k is any natural number.
Assume 2 divides F3k for k = 1,2,3,...,k.
C. Induction step
Proof for F3(k+1) is also true
F3(k+1) = F3k+3
F3k+3 = F(3k+3)-2 + F(3k+3)-1
F3k+3 = F3k+1 + F3k+2
F3k+3 = (F3k-1+F3k) + (F3k+F3k+1) (Subtitution using Fn = Fn-2 + Fn-1)
F3k+3 = (F3k-1+F3k) + (F3k+[F3k-1+F3k])
F3k+3 = 2*F3k-1 + 3*F3k
Because 2 divides F3k(from assumption), therefore F3k = 2q, q is any natural number.
F3k+3 = 2*F3k-1 + 3*2q
F3k+3 = 2*(F3k-1+3q)
for k+1 the statement is true,
Hence, 2 divides F3k for k is any natural number, therefore if 3 divides n, then 2 divides Fn for n>=3 (proved)
Does my induction step is enough to prove the statement?
Or are there more appropriate ways to prove the statement?
Fn = Fn-2 + Fn-1,
For all natural number n >= 3, This sequence is called the Fibonacci sequence. Show
that if 3 divides n, then 2 divides Fn. You may use any suitable proof technique.
My Answer :
I use strong induction to proof
Proof :
A. Base n=3
F3 = F2 + F1
F3 = 1 + 1 = 2, so, the statement is true for the base
B. Induction hypothesis
3 divides n. Therefore, n can be expressed: n = 3k, for k is any natural number.
Assume 2 divides F3k for k = 1,2,3,...,k.
C. Induction step
Proof for F3(k+1) is also true
F3(k+1) = F3k+3
F3k+3 = F(3k+3)-2 + F(3k+3)-1
F3k+3 = F3k+1 + F3k+2
F3k+3 = (F3k-1+F3k) + (F3k+F3k+1) (Subtitution using Fn = Fn-2 + Fn-1)
F3k+3 = (F3k-1+F3k) + (F3k+[F3k-1+F3k])
F3k+3 = 2*F3k-1 + 3*F3k
Because 2 divides F3k(from assumption), therefore F3k = 2q, q is any natural number.
F3k+3 = 2*F3k-1 + 3*2q
F3k+3 = 2*(F3k-1+3q)
for k+1 the statement is true,
Hence, 2 divides F3k for k is any natural number, therefore if 3 divides n, then 2 divides Fn for n>=3 (proved)
Does my induction step is enough to prove the statement?
Or are there more appropriate ways to prove the statement?