Help me prove this statement about Fibonacci sequence

[Akmal06]

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?

 

[lev888]

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?

If you are doing induction on k, then, I think, your statement should be rewritten using k.
Induction step is very confusing because of inconsistent use of parentheses.

 

[Akmal06]

Suppose that [MATH] F1 = F2 = 1 [/MATH] and that
[MATH]F_{n} = F_{n-2} + F_{n-1} [/MATH],
For all natural number n >= 3, This sequence is called the Fibonacci sequence. Show
that \(if\: 3\: |\: n\:, \:then\: 2 \:| \:Fn\: \). You may use any suitable proof technique.

My Answer :
I use induction to prove
Proof :
A. Base n=3

[MATH] F_{3} = F_{2} + F{1}\\ F_{3} = 1 + 1 \\ F_{3} = 2 [/MATH] so, the statement is true for the base

B. Induction hypothesis
[MATH] 3\: |\: n [/MATH]. Therefore, n can be expressed: \(n = 3m,\: for \: m \in \mathbb{N} \)
Assume \(2\: | \:F_{3k}\: for\: m\: =\: k\)

C. Induction step
Proof for \(F_{3(k+1)}\) is also true

[MATH] F_{3(k+1)} = F_{3k+3} \\ F_{3k+3} = F_{(3k+3)-2} + F_{(3k+3)-1} \\ F_{3k+3} = F_{3k+1} + F_{3k+2} [/MATH] From fibonacci formula, \(F_{3k+2} \:= \:F_{3k} \:+ \:F_{3k+1}\). We can do subtitution.

[MATH] F_{3k+3} = F_{3k+1} + F_{3k}+F_{3k+1} \\ F_{3k+3} = 2*F_{3k+1} + F_{3k} \\ [/MATH] Because \( 2 \: |\: F_{3k}\) (from assumption), \(F_{3k}\: =\: 2q, \: q \in \mathbb{N}.\)

[MATH] F_{3k+3} = 2*F_{3k-1} + 2*q \\ F_{3k+3} = 2*(F_{3k-1} + q) \\ [/MATH] for k+1 the statement is true,
Hence, \(\:2\: |\: F_{3k} \:for\: k \in \mathbb{N}\). Therefore, \(if \: 3 \: | \: n, \: then \:2 \: | \: 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?

 

[Cubist]

I can follow your logic, and I personally think the proof is good, well done. I can't think of a better way to prove this.

I notice that you've started several threads on this topic. Please post any updates within a single thread (since it's a single question).

A small suggestion is to shorten the following, since everyone knows that an even+even=even, so instead of...

[MATH] F_{3k+3} = 2*F_{3k+1} + F_{3k} [/MATH] Because \( 2 \: |\: F_{3k}\) (from assumption), \(F_{3k}\: =\: 2q, \: q \in \mathbb{N}.\)

[MATH] F_{3k+3} = 2*F_{3k-1} + 2*q \\ F_{3k+3} = 2*(F_{3k-1} + q) \\ [/MATH] for k+1 the statement is true,

you could simply state...

[MATH] F_{3(k+1)} = 2*F_{3k+1} + F_{3k} [/MATH]
It follows that \(2 \: | \: F_{3(k+1)}\), since \( 2 \: |\: F_{3k}\) (from the assumption).

Therefore for k+1 the statement is also true

...then continue with your closing statement.

 

[Akmal06]

Thank you for your answer. It's very helpful. I'm sorry for posting several threads because in the first and second threads i haven't used LaTeX, so people get confused. Then in the final thread i learn LaTeX and use it, so people can understand easily.
Once more, i very thank to you, it is very helpful