Results 1 to 5 of 5

Math Help - Proof using Strong Mathematical Induction

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    2

    Proof using Strong Mathematical Induction

    I would greatly appreciate some direction or hints to finish this problem.

    Let n be a natural number such that n>5. Show that Fn=5Fn-4+3Fn-5. (Where all n, n-4, and n-5 are subscripts of F)

    I know I need to proceed by way of strong mathematical induction.

    Base Case: Suppose n=6. Then, F(6)=5F(6-4)+3F(6-5)= 5F(2)+3F(1).

    Now I'm stuck. I'm not even sure how to establish the base case. I realize typically you just show that the statement is true for a variable. However, I don't know how to show the equivalency here. Should I set the Fn equal to a value?

    I appreciate any help.!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by mathmajor2010 View Post
    I would greatly appreciate some direction or hints to finish this problem.

    Let n be a natural number such that n>5. Show that Fn=5Fn-4+3Fn-5. (Where all n, n-4, and n-5 are subscripts of F)

    I know I need to proceed by way of strong mathematical induction.

    Base Case: Suppose n=6. Then, F(6)=5F(6-4)+3F(6-5)= 5F(2)+3F(1).

    Now I'm stuck. I'm not even sure how to establish the base case. I realize typically you just show that the statement is true for a variable. However, I don't know how to show the equivalency here. Should I set the Fn equal to a value?

    I appreciate any help.!


    It'd be a great idea if you didn't assume everybody understands your notation and define what os F_n...Fibonacci sequence or what!?

    And use parentheses: you actually meant F_n=5F_{n-4}+3F_{n-5} , so if your Fibonacci sequence is

    1,1,2,3,5,8,13,21,34, 55,..., then F_6=8=5F_2+3F_1=5\cdot 1+3\cdot 1 and you have the base case.

    Suppose truthness for k<n , and take F_{n+1}:=F_n+F_{n-1} . The inductive hypotheses tells us that both terms in the RHS fulfill the equality, so:

    F_{n+1}=F_n+F_{n-1}=5F_{n-4}+3F_{n-5}+5F_{n-5}+3F_{n-6} ...and now just rearrange these terms and use the definition of Fibonacci sequence...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2010
    Posts
    2
    Quote Originally Posted by tonio View Post
    It'd be a great idea if you didn't assume everybody understands your notation and define what os F_n...Fibonacci sequence or what!?

    And use parentheses: you actually meant F_n=5F_{n-4}+3F_{n-5} , so if your Fibonacci sequence is

    1,1,2,3,5,8,13,21,34, 55,..., then F_6=8=5F_2+3F_1=5\cdot 1+3\cdot 1 and you have the base case.

    Suppose truthness for k<n , and take F_{n+1}:=F_n+F_{n-1} . The inductive hypotheses tells us that both terms in the RHS fulfill the equality, so:

    F_{n+1}=F_n+F_{n-1}=5F_{n-4}+3F_{n-5}+5F_{n-5}+3F_{n-6} ...and now just rearrange these terms and use the definition of Fibonacci sequence...
    I'm very sorry for the misunderstanding. Hopefully this will be better.

    How did you get the addition 5F_{n-5}+3F_{n-6} ? would it not be F5_{n-3}+3F_{n-4}?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by mathmajor2010 View Post
    I'm very sorry for the misunderstanding. Hopefully this will be better.

    How did you get the addition 5F_{n-5}+3F_{n-6} ? would it not be F5_{n-3}+3F_{n-4}?

    Just input n-1 instead n in the formula...and be very careful with minus signs!

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    In fact, the proof can be derived without using induction at all. Just sum up two consecutive Fibonacci numbers whenever they occur.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof by strong induction
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 27th 2011, 04:06 PM
  2. Strong Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: August 22nd 2010, 12:40 AM
  3. Proof by strong induction?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 5th 2009, 07:51 AM
  4. Proof Using Strong Induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 27th 2009, 06:30 AM
  5. Strong induction proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 7th 2008, 09:48 PM

Search Tags


/mathhelpforum @mathhelpforum