Results 1 to 2 of 2

Thread: Induction Help!

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    30

    Induction Help!

    Sorry for all of these induction promblems, i have a couple of more questions, and as an respected remember recommended, i will attempt these promblems.


    =============================

    Define the sequence F as follows:

    $\displaystyle F_1=1, F_2=1, F_n=F_n-1 + F_(n-2) n >= 3 $

    Prove that

    $\displaystyle F_1^2+F_2^2+... F_n^2 = F_nF_(n+1) whenever n is a positive integer.$


    Here is what i did

    1. P(n): $\displaystyle F_1^2+F_2^2+... F_n^2 = F_nF_(n+1)$
    2. P(3) $\displaystyle F_3^2 = F_3F_3+1 $ Im confused on this step, i got $\displaystyle F_9 = F_3F_4 $
    3. Assume: P(n): $\displaystyle F_1^2+F_2^2+... F_n^2 = F_nF_(n+1)$
    4. Prove P(n+1)
    $\displaystyle F_n+F_n+1+F_(n+1)^2 = F_n+1F_n+2$ // replaces right hand side of the original equation up to teh summation of the left hand side
    $\displaystyle f_n+1[F_n+F_n+1+F_n+1 = F_n+1F_n+2 $ // Factored out $\displaystyle F_n+1$. Im stucked, i need pointers on step 2 and 4, thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Fibonacci Sequence

    Hello tokio
    Quote Originally Posted by tokio View Post
    Sorry for all of these induction promblems, i have a couple of more questions, and as an respected remember recommended, i will attempt these promblems.


    =============================

    Define the sequence F as follows:

    $\displaystyle F_1=1, F_2=1, F_n=F_n-1 + F_(n-2) n >= 3 $

    Prove that

    $\displaystyle F_1^2+F_2^2+... F_n^2 = F_nF_(n+1) whenever n is a positive integer.$


    Here is what i did

    1. P(n): $\displaystyle F_1^2+F_2^2+... F_n^2 = F_nF_(n+1)$
    2. P(3) $\displaystyle F_3^2 = F_3F_3+1 $ Im confused on this step, i got $\displaystyle F_9 = F_3F_4 $
    3. Assume: P(n): $\displaystyle F_1^2+F_2^2+... F_n^2 = F_nF_(n+1)$
    4. Prove P(n+1)
    $\displaystyle F_n+F_n+1+F_(n+1)^2 = F_n+1F_n+2$ // replaces right hand side of the original equation up to teh summation of the left hand side
    $\displaystyle f_n+1[F_n+F_n+1+F_n+1 = F_n+1F_n+2 $ // Factored out $\displaystyle F_n+1$. Im stucked, i need pointers on step 2 and 4, thanks.
    Thanks for showing us your attempt. The sequence is the well-known Fibonacci Sequence, each of whose terms is the sum of the two preceding terms. So the sequence looks like this:

    $\displaystyle 1, 1, 2, 3, 5, 8, 13, 21, ...$

    So, with $\displaystyle P(n)$ defined as you have done:

    $\displaystyle P(3) = 1^2 + 1^2 + 2^2 = 1 + 1 + 4 = 6 = 2 \times 3 = F_3 \times F_4$

    So $\displaystyle P(3)$ is true.

    Now for the induction part:

    $\displaystyle P(n) \Rightarrow F_1^2 + F_2^2 + ... + F_n^2 + F_{n+1}^2 = F_nF_{n+1}+F_{n+1}^2$

    $\displaystyle = F_{n+1}(F_n + F_{n+1})$

    $\displaystyle = F_{n+1}F_{n+2}$, since $\displaystyle F_{n+2}=$ the sum of the two preceding terms, $\displaystyle F_{n+1} + F_n$

    $\displaystyle = F_{n+1}F_{(n+1)+1}$

    $\displaystyle \Rightarrow P(n+1)$

    Since we have already shown that $\displaystyle P(3)$ is true, this completes the proof.

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: Apr 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Apr 19th 2010, 05:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 7th 2008, 04:10 PM

Search Tags


/mathhelpforum @mathhelpforum