Results 1 to 5 of 5

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

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    9

    Talking [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!!
    Last edited by MathGeezer; March 20th 2009 at 11:42 AM. Reason: Problem Solved
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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:

    Quote Originally Posted by chisigma View Post
    \sum_{k=0}^{n} \binom {n}{k} \cdot F_{k}= F_{2n} (1)
    See here

    Quote Originally Posted by chisigma View Post
    \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}<br />
   1 & 1  \\<br />
   1 & 0  \\<br /> <br />
 \end{array} } \right) )



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

    And it follows that we have: <br />
\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}<br />

    From there check that <br />
f_{n \cdot m} <br />
is a multiple of <br />
f_m <br />
    Last edited by PaulRS; March 11th 2009 at 05:52 AM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by MathGeezer View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2008
    From
    Guernsey
    Posts
    69
    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: May 4th 2011, 02:02 PM
  2. [SOLVED] Fibonacci numbers...help plz
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 21st 2009, 10:00 AM
  3. [SOLVED] Fibonacci
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 24th 2009, 09:20 AM
  4. Fibonacci sequence - prove by induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 23rd 2008, 05:19 PM
  5. Replies: 5
    Last Post: June 22nd 2008, 07:04 AM

Search Tags


/mathhelpforum @mathhelpforum