Results 1 to 2 of 2

Math Help - 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:

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

    Prove that

     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): F_1^2+F_2^2+... F_n^2 = F_nF_(n+1)
    2. P(3) F_3^2 = F_3F_3+1 Im confused on this step, i got  F_9 = F_3F_4
    3. Assume: P(n): F_1^2+F_2^2+... F_n^2 = F_nF_(n+1)
    4. Prove P(n+1)
     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
    f_n+1[F_n+F_n+1+F_n+1 = F_n+1F_n+2 // Factored out 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:

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

    Prove that

     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): F_1^2+F_2^2+... F_n^2 = F_nF_(n+1)
    2. P(3) F_3^2 = F_3F_3+1 Im confused on this step, i got  F_9 = F_3F_4
    3. Assume: P(n): F_1^2+F_2^2+... F_n^2 = F_nF_(n+1)
    4. Prove P(n+1)
     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
    f_n+1[F_n+F_n+1+F_n+1 = F_n+1F_n+2 // Factored out 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:

    1, 1, 2, 3, 5, 8, 13, 21, ...

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

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

    So P(3) is true.

    Now for the induction part:

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

    = F_{n+1}(F_n + F_{n+1})

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

    = F_{n+1}F_{(n+1)+1}

    \Rightarrow P(n+1)

    Since we have already shown that 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: April 21st 2011, 01:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 06:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2008, 05:10 PM

Search Tags


/mathhelpforum @mathhelpforum