Results 1 to 2 of 2

Thread: Fibonacci proof

  1. #1
    Junior Member
    Joined
    Oct 2007
    Posts
    37
    Awards
    1

    Fibonacci proof

    Here is my latest problem. Little help please. NOTE: u(n) is read u "sub" n

    Prove by induction that u(n) is even if 3 divides n. In addition I also have a logic question just in reading this problem.

    Is (3 divides n implies u(n) is even) the same thing as
    u(n) is even if 3 divides n.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    849
    Hello, padsinseven!

    Your interpretation of that implication is correct.


    Prove by induction that $\displaystyle u_n$ is even if 3 divides $\displaystyle n$.

    We wish to prove that: .If $\displaystyle n = 3k$, then $\displaystyle u_n$ is even.


    Verify $\displaystyle S(1)\!:\;k = 1,\:n = 3\quad\Rightarrow\quad u_3 \:=\:2$ . . . True!


    Assume $\displaystyle S(k)$ is true: .$\displaystyle u_{3k} \:=\:2a$ for some integer $\displaystyle a.$

    . . and we wish to prove that: .$\displaystyle u_{3(k+1)}$ is even.


    We have: .$\displaystyle u_{3(k+1)} \;=\;u_{3k+3}$

    . . . . . . . . . . . . $\displaystyle = \;\underbrace{u_{3k+2}} +\, u_{3k+1} $

    . . . . . . . . . . $\displaystyle =\;\overbrace{\left(u_{3k+1} + u_{3k}\right)} +\, u_{3k+1} $

    . . . . . . . . . . $\displaystyle =\;2\!\cdot\!u_{3k+1} + \underbrace{u_{3k}}_{\text{This is }2a}$

    . . . . . . . . . . $\displaystyle = \;2\!\cdot\!u_{3k+1} + 2a$

    . . . . . . . . . . $\displaystyle = \;2\left(u_{3k+1} + a\right)$


    Therefore: .$\displaystyle u_{3(k+1)}$ is even.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Nov 28th 2009, 10:21 PM
  2. Need help on Fibonacci proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Apr 23rd 2009, 08:31 AM
  3. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 2nd 2008, 05:12 PM
  4. Fibonacci proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 26th 2007, 07:37 AM
  5. another fibonacci proof
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Oct 16th 2007, 07:10 AM

Search Tags


/mathhelpforum @mathhelpforum