[SOLVED] Fibonacci. Prove: If 3|n, then 2|Fn

**MathGeezer** · March 8th 2009, 11:49 PM

Prove that if Fn is the "nth" Fibonacci number that if 3|n (3 divides n) then 2|Fn
(2 divides the nth Fibonacci number).

THIS PROBLEM HAS BEEN SOLVED.

THANKS TO ALL WHO HELPED!!

**chisigma** · March 11th 2009, 02:38 AM

In…

http://mathworld.wolfram.com/FibonacciNumber.html

… you can find the following ‘finite sums’…

$\sum_{k=0}^{n} \binom {n}{k} \cdot F_{k}= F_{2n}$ (1)

$\sum_{k=0}^{n} \binom {n}{k} \cdot 2^{k}\cdot F_{k}= F_{3n}$ (2)

Since $F_{0}=0$ , it follows from (2) that $2$ devides $F_{3n}$ …

Regards

**PaulRS** · March 11th 2009, 03:38 AM

Read this post here, it is even more general than what you need. (It uses the Euclidean Algorithm)

Proofs for the formulas that appear above in this thread:

Originally Posted by chisigma

$\sum_{k=0}^{n} \binom {n}{k} \cdot F_{k}= F_{2n}$ (1)

See here

Originally Posted by chisigma

$\sum_{k=0}^{n} \binom {n}{k} \cdot 2^{k}\cdot F_{k}= F_{3n}$ (2)

Simply consider $(2\cdot F+\text{Id})^n$ . We have $2\cdot F+\text{Id}=F^3$ , the rest follows like in the previous link.

(Again $F = \left( {\begin{array}{*{20}c} 1 & 1 \\ 1 & 0 \\ \end{array} } \right)$ )

In fact this gets even more general since we have: $ f_{m } \cdot F + f_{m-1} \cdot {\rm{Id}} = F^m $ (this may be proven by induction quite easily since
$ F^2 = F + {\rm{Id}} $ ) thus: $ \left( {f_{m } \cdot F + f_{m-1} \cdot {\rm{Id}}} \right)^n = F^{n \cdot m} $

And it follows that we have: $ \sum\limits_{k = 0}^n {\binom{n}{k}\cdot f_{m } ^k\cdot f_k \cdot f_{m-1} ^{n - k} } =f_{n\cdot m} $

From there check that $ f_{n \cdot m} $ is a multiple of $ f_m $

**awkward** · March 15th 2009, 12:21 PM

Originally Posted by MathGeezer

I'm stalled on writing a couple Fibonacci proofs for a paper I'm working on.

Specifically, if Fn is the "nth" Fibonacci number I need to prove:

1) That if 3|n (3 is a factor of n) then 2|Fn (2 is a factor of the nth Fibonacci number).
[snip]

Since

$F_{3n} = F_{3n-1} + F_{3n-2} = F_{3n-2} + F_{3n-3} + F_{3n-2} = 2 F_{3n-2} + F_{3n-3}$

the result follows easily by induction on $n$ .

**SimonM** · March 16th 2009, 07:55 AM

Alternatively, consider the Fibonacci sequence modulo 2.

The first few terms are

$1,1,0,1,1,0,1,1,0,\ldots$

Can you spot a pattern and prove it?

Thread: [SOLVED] Fibonacci. Prove: If 3|n, then 2|Fn

LinkBack

Thread Tools

Display

[SOLVED] Fibonacci. Prove: If 3|n, then 2|Fn

Similar Math Help Forum Discussions

prove any 2 successive terms of fibonacci sequence are relatively prime

[SOLVED] Fibonacci numbers...help plz

[SOLVED] Fibonacci

Fibonacci sequence - prove by induction

Prove that the gcd of two consecutive Fibonacci numbers is 1.

Search Tags