Results 1 to 8 of 8

Math Help - Mathematical Induction for Fibonacci sequence

  1. #1
    Junior Member
    Joined
    Oct 2010
    Posts
    43

    Mathematical Induction for Fibonacci sequence[SOLVED]

    Ok, this looks different from my other problems with inductions.
    Suppose Fn, n is greater or equal to 0 is the Fibonacci sequence (i.e. F0=F1 = 1, and Fn = Fn-1 + Fn-2 for n is greater or equal to 2). Use mathematical induction to prove that
    (Fn+2)(Fn)-F^2 * n+1 = (-1)^n for all n greater or equal to 0.

    Would I need to change the left side using characteristic equation?

    The left side and right side are equal when using the base case = 0. i tried the p(k) and p(k+1) method but looks like I'll need to use a different equation on the left hand side.
    Last edited by hellfire127; December 1st 2010 at 07:21 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by hellfire127 View Post
    Ok, this looks different from my other problems with inductions.
    Suppose Fn, n is greater or equal to 0 is the Fibonacci sequence (i.e. F0=F1 = 1, and Fn = Fn-1 + Fn-2 for n is greater or equal to 2). Use mathematical induction to prove that
    (Fn+2)(Fn)-F^2 * n+1 = (-1)^n for all n greater or equal to 0.

    Would I need to change the left side using characteristic equation?

    The left side and right side are equal when using the base case = 0. i tried the p(k) and p(k+1) method but looks like I'll need to use a different equation on the left hand side.
    F_{n+2}F_n-F^2_{n+1}=[F_{n+1}+F_n][F_{n-1}+F_{n-2}]-(F_n+F_{n-1})^2=

    =F_{n+1}F_{n-1}+F_{n+1}F_{n-2}+F_nF_{n-1}+F_nF_{n-2}-F_n^2-2F_nF_{n-1}-F^2_{n-1}=

    =F_{n+1}F_{n-1}-F^2_n+F_nF_{n-2}-F^2_{n-1}+F_{n+1}F_{n-2}-F_nF_{n-1}=

    =(-1)^{n-1}+(-1)^{n-2}+(F_n+F_{n-1})F_{n-2}-F_nF_{n-1}=

    =(-1)^{n-2}(-1+1)+F_nF_{n-2}-F_{n-1}(F_{n-2}-F_n)=F_nF_{n-2}-F_{n-1}^2=(-1)^{n-2}

    The inductive hypothesis is that the claim is true for all k<n , and we prove it for k=n

    Check carefully, slowly and well the above, prove every step and...voila!

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2010
    Posts
    43
    hmmm, i'll have to check carefully each step as i'm already lost on the 3rd. the reordering is a bit confusing but ill get it eventually. thanks!

    edit: well after looking at it for an hour i still don't see how it reaches that. i will just have to skip this problem for now.
    Last edited by hellfire127; November 30th 2010 at 07:05 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Oct 2010
    Posts
    43
    is there another way to show the solution above? i'm having a hard time going from one step to another. i understand the process for Fn-1 + Fn-2 but this just doesn't seem to work with the induction process for me.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by hellfire127 View Post
    is there another way to show the solution above? i'm having a hard time going from one step to another. i understand the process for Fn-1 + Fn-2 but this just doesn't seem to work with the induction process for me.
    1) You must master thoroughly high school algebra

    2) You must understand perfectly well how Fibonacci Series work.

    Write down what I posted in my 1st message you and, if after some further effort, you're still

    lost write back pointing out where exactly you got stuck.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by hellfire127 View Post
    Ok, this looks different from my other problems with inductions.
    Suppose Fn, n is greater or equal to 0 is the Fibonacci sequence (i.e. F0=F1 = 1, and Fn = Fn-1 + Fn-2 for n is greater or equal to 2). Use mathematical induction to prove that
    (Fn+2)(Fn)-F^2 * n+1 = (-1)^n for all n greater or equal to 0.

    Would I need to change the left side using characteristic equation?

    The left side and right side are equal when using the base case = 0. i tried the p(k) and p(k+1) method but looks like I'll need to use a different equation on the left hand side.
    Here is another way;

    P(k)

    F_{k+2}\;F_k-\left(F_{k+1}\right)^2=(-1)^k


    P(k+1)

    F_{k+3}\;F_{k+1}-\left(F_{k+2}\right)^2=(-1)^{k+1}=(-1)(-1)^k


    Proof

    Try to show that P(k+1) will be true if P(k) is true,
    hence write P(k+1) in terms of P(k).

    F_{k+3}=F_{k+1}+F_{k+2}

    F_{k+2}=F_{k+1}+F_k}

    therefore, rewriting P(k+1)

    \left(F_{k+1}+F_{k+2}\right)F_{k+1}-\left(F_{k+1}+F_k\right)\left(F_{k+1}+F_k\right)=-(-1)^k ?

    \left(F_{k+1}\right)^2+F_{k+2}\;F_{k+1}-\left[\left(F_{k+1}\right)^2+2F_k\;F_{k+1}+\left(F_k\rig  ht)^2\right]=-(-1)^k ?

    F_{k+2}\;F_{k+1}-2F_k\;F_{k+1}-\left(F_k\right)^2=-(-1)^k ?

    \left(F_k\right)^2+2F_k\;F_{k+1}-F_{k+2}\;F_{k+1}=(-1)^k ?

    If we now write F_{k+2} in terms of F_{k+1}, we will obtain the \left(F_{k+1}\right)^2 term in P(k)...

    F_{k+1}+F_k=F_{k+2}

    \Rightarrow\ \left(F_k\right)^2+2F_k\;F_{k+1}-\left(F_k+F_{k+1}\right)F_{k+1}=\left(F_k\right)^2  +2F_k\;F_{k+1}-F_k\;F_{k+1}-\left(F_{k+1}\right)^2

    =\left(F_k\right)^2+F_k\;F_{k+1}-\left(F_{k+1}\right)^2

    Factoring out F_k

    F_k\left(F_k+F_{k+1}\right)-\left(F_{k+1}\right)^2=F_k\;F_{k+2}-\left(F_{k+1}\right)^2

    Hence if P(k) is true, P(k+1) will certainly be true.

    Test the base case.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2010
    Posts
    43
    Quote Originally Posted by Archie Meade View Post
    Here is another way;

    P(k)

    F_{k+2}\;F_k-\left(F_{k+1}\right)^2=(-1)^k


    P(k+1)

    F_{k+3}\;F_{k+1}-\left(F_{k+2}\right)^2=(-1)^{k+1}=(-1)(-1)^k


    Proof

    Try to show that P(k+1) will be true if P(k) is true,
    hence write P(k+1) in terms of P(k).

    F_{k+3}=F_{k+1}+F_{k+2}

    F_{k+2}=F_{k+1}+F_k}

    therefore, rewriting P(k+1)

    \left(F_{k+1}+F_{k+2}\right)F_{k+1}-\left(F_{k+1}+F_k\right)\left(F_{k+1}+F_k\right)=-(-1)^k ?

    \left(F_{k+1}\right)^2+F_{k+2}\;F_{k+1}-\left[\left(F_{k+1}\right)^2+2F_k\;F_{k+1}+\left(F_k\rig  ht)^2\right]=-(-1)^k ?

    F_{k+2}\;F_{k+1}-2F_k\;F_{k+1}-\left(F_k\right)^2=-(-1)^k ?

    \left(F_k\right)^2+2F_k\;F_{k+1}-F_{k+2}\;F_{k+1}=(-1)^k ?

    If we now write F_{k+2} in terms of F_{k+1}, we will obtain the \left(F_{k+1}\right)^2 term in P(k)...

    F_{k+1}+F_k=F_{k+2}

    \Rightarrow\ \left(F_k\right)^2+2F_k\;F_{k+1}-\left(F_k+F_{k+1}\right)F_{k+1}=\left(F_k\right)^2  +2F_k\;F_{k+1}-F_k\;F_{k+1}-\left(F_{k+1}\right)^2

    =\left(F_k\right)^2+F_k\;F_{k+1}-\left(F_{k+1}\right)^2

    Factoring out F_k

    F_k\left(F_k+F_{k+1}\right)-\left(F_{k+1}\right)^2=F_k\;F_{k+2}-\left(F_{k+1}\right)^2

    Hence if P(k) is true, P(k+1) will certainly be true.

    Test the base case.
    oh wow thank you. i see how you got to the end by following the steps. i think the k+1 helped as well. thanks again!
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    I had a suspicion that I had rewritten too many terms,
    so there is a more compact proof....


    P(k)

    F_{k+2}\;F_k-\left(F_{k+1}\right)^2=(-1)^k


    P(k+1)

    F_{k+3}\;F_{k+1}-\left(F_{k+2}\right)^2=(-1)^{k+1}=-(-1)^k


    Proof

    We only require rewriting

    F_{k+3}=F_{k+2}+F_{k+1}

    Hence...

    \left(F_{k+2}+F_{k+1}\right)F_{k+1}-\left(F_{k+2}\right)^2=-(-1)^k ?

    F_{k+2}\;F_{k+1}+\left(F_{k+1}\right)^2-\left(F_{k+2}\right)^2=-(-1)^k ?

    Factoring F_{k+2}

    F_{k+2}\left(F_{k+1}-F_{k+2}\right)+\left(F_{k+1}\right)^2=-(-1)^k ?

    Multiplying both sides by -1

    F_{k+2}\left(F_{k+2}-F_{k+1}\right)-\left(F_{k+1}\right)^2=(-1)^k ?

    Using F_{k+2}=F_k+F_{k+1}\Rightarrow\ F_{k+2}-F_{k+1}=F_k

    \Rightarrow\ F_{k+2}\;F_k-\left(F_{k+1}\right)^2=(-1)^k

    Hence P(k) being true causes P(k+1) to be true.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Sequence - Induction Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 19th 2011, 03:41 PM
  2. [SOLVED] Fibonacci sequence induction proof
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 1st 2010, 10:22 AM
  3. Replies: 2
    Last Post: March 1st 2010, 11:57 AM
  4. Fibonacci Sequence: Induction Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 14th 2009, 07:38 AM
  5. Fibonacci sequence - prove by induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 23rd 2008, 05:19 PM

Search Tags


/mathhelpforum @mathhelpforum