# Fibonacci sequence divisibility proof

• Jun 18th 2011, 10:11 AM
panglot
Fibonacci sequence divisibility proof
Hello All,

I am thoroughly lost with how to construct this proof:

Let F(sub)n be the nth Fibonacci number.

Prove that, if 3|n then 2|F(sub)n.

Would induction be a recommendation, and if so, could anyone please recommend a base assumption to begin with?

Thank you very much for your time,

Panglot
• Jun 18th 2011, 10:31 AM
Also sprach Zarathustra
Re: Fibonacci sequence divisibility proof
Quote:

Originally Posted by panglot
Hello All,

I am thoroughly lost with how to construct this proof:

Let F(sub)n be the nth Fibonacci number.

Prove that, if 3|n then 2|F(sub)n.

Would induction be a recommendation, and if so, could anyone please recommend a base assumption to begin with?

Thank you very much for your time,

Panglot

If and only if can be placed.

Are you familiar with the theorem that says:

\$\displaystyle F_m|F_n\$ if and only if \$\displaystyle m|n\$.
• Jun 19th 2011, 06:14 AM
HallsofIvy
Re: Fibonacci sequence divisibility proof
What you want to prove is that
\$\displaystyle F_{3n}\$
is divisible by 2 for any positive integer n. It is easy to do that by induction on n.

If n= 1,
\$\displaystyle F_{3(1)}= F_3= 2\$
which is divisible by 2.

Assume that, for some k,
\$\displaystyle F_{3k}\$
is divisible by 2. That is, that
\$\displaystyle F_{3k}= 2m\$
for some integer m.

Then
\$\displaystyle F_{3(k+1)}= F_{3k+ 3}= F_{3k+1}+ F_{3k+2}= F_{3k+1}+ (F_{3k}+ F_{3k+1})= 2m+ 2F_{3k+1}\$.
• Jun 19th 2011, 07:59 PM
panglot
Re: Fibonacci sequence divisibility proof
Quote:

Originally Posted by HallsofIvy
What you want to prove is that
\$\displaystyle F_{3n}\$
is divisible by 2 for any positive integer n. It is easy to do that by induction on n.

If n= 1,
\$\displaystyle F_{3(1)}= F_3= 2\$
which is divisible by 2.

Assume that, for some k,
\$\displaystyle F_{3k}\$
is divisible by 2. That is, that
\$\displaystyle F_{3k}= 2m\$
for some integer m.

Then
\$\displaystyle F_{3(k+1)}= F_{3k+ 3}= F_{3k+1}+ F_{3k+2}= F_{3k+1}+ (F_{3k}+ F_{3k+1})= 2m+ 2F_{3k+1}\$.

I'm sorry, but I don't quite follow how you arrived at the last two in the series of equivalences:

= F_{3k+1}+ (F_{3k}+ F_{3k+1})= 2m+ 2F_{3k+1}
• Jun 20th 2011, 04:46 AM
Also sprach Zarathustra
Re: Fibonacci sequence divisibility proof
Quote:

Originally Posted by panglot
I'm sorry, but I don't quite follow how you arrived at the last two in the series of equivalences:

= F_{3k+1}+ (F_{3k}+ F_{3k+1})= 2m+ 2F_{3k+1}

By definition of Fibonacci sequence.

F_{k+2}=F_{k+1}+F_{k}.