# Math Help - [SOLVED] Fibonacci. Prove: If 3|n, then 2|Fn

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

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!!

2. 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

3. 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
$

4. 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$.

5. 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?
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 19, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9752037525177002, "perplexity": 1963.0145498047623}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2016-30/segments/1469257832399.72/warc/CC-MAIN-20160723071032-00164-ip-10-185-27-174.ec2.internal.warc.gz"}