Results 1 to 5 of 5

Math Help - simple proof help (I think I'm really close)

  1. #1
    Junior Member
    Joined
    Sep 2007
    Posts
    30

    simple proof help (I think I'm really close)

    Suppose that h_0, h_1, h_2, h_3, \dots is a sequence defined as follows: h_0 = 1, h_1 = 2, h_2 = 3, h_k = h_{k-1}+h_{k-2}+h_{k-3} for all ints k \geq 3. Prove that h_n\leq 3^n for all ints n \geq 0

    What I have so far is:

    base case n=0, then h_0=1 and 1 \leq 3.

    inductive step:
    assume true for the base case, then h_{n+1} = h_{(n+1)-1} + h_{(n+1)-2} + h_{(n+1)-3} = h_{n} + h_{n-1} + h_{n-2}

    since the base case is \leq 3^n, we really just want to show that our inductive case is \leq 3^{n+1} = 3 \times 3^n

    but how can I show that h_{n+1} \leq 3^{n+1}?

    any help with this would be greatly appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member arpitagarwal82's Avatar
    Joined
    Feb 2009
    Posts
    103
    We will use Mathematical induction to proove this. But here you dont just have to asume that its true for k and prove for k+1. Here we have to use the extended case of MI.

    Assume S_n is a statement that h_n\leq 3^n

    Now show that S_0, S_1 and S_2 is correct. (which infact is)



    Now assume
    S_{k-1}, S_{k-2} and S_{k-3} are true.
    i.e.
    h_{k-1} \leq 3^{k-1}
    h_{k-2}\leq 3^{k-2}
    h_{k-3}\leq 3^{k-3}


    Now prove that S_k is trure.
    To proove
    h_k \leq 3^k

    now h_k = h_{k-1}+h_{k-2}+h_{k-3}
    => h_k \leq 3^{k-1} + 3^{k-2} + 3^{k-3}

    Now in a few step you can show that S_k is true. hence proved.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by arpitagarwal82 View Post
    We will use Mathematical induction to proove this. But here you dont just have to asume that its true for k and prove for k+1. Here we have to use the extended case of MI.

    Assume S_n is a statement that h_n\leq 3^n

    Now show that S_0, S_1 and S_2 is correct. (which infact is)



    Now assume
    S_{k-1}, S_{k-2} and S_{k-3} are true.
    i.e.
    h_{k-1} \leq 3^{k-1}
    h_{k-2}\leq 3^{k-2}
    h_{k-3}\leq 3^{k-3}


    Now prove that S_k is trure.
    To proove
    h_k \leq 3^k

    now h_k = h_{k-1}+h_{k-2}+h_{k-3}
    => h_k \leq 3^{k-1} + 3^{k-2} + 3^{k-3}

    Now in a few step you can show that S_k is true. hence proved.
    There is no need to use the extended version of MI. Just make S_n the statement: h_k<3^k for all k: 0 \le k\le n. Then the base case is S_2, and so on.

    CB
    Last edited by CaptainBlack; February 26th 2009 at 11:36 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member arpitagarwal82's Avatar
    Joined
    Feb 2009
    Posts
    103
    Quote Originally Posted by CaptainBlack View Post
    There is no need to use the extended version of MI. Just make S_n the statement: h_k<3^k for all k: 0 \le k\le n. Then the base case is S_2, and so on.

    CB
    But n this problem, you cannot just assume S_n to be correct for any general integer k and prove that S_{k+1} is true. It would be impossible.

    You have to assume that statement is true fr three cnsicutive integers ( I took k-3, k-2, k-1) and show that statement is true for fourth consecutive integer (k in my case).

    Also you have to show that statement is true for first three integers.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by arpitagarwal82 View Post
    But n this problem, you cannot just assume S_n to be correct for any general integer k and prove that S_{k+1} is true. It would be impossible.

    You have to assume that statement is true fr three cnsicutive integers ( I took k-3, k-2, k-1) and show that statement is true for fourth consecutive integer (k in my case).
    Here we would be assuming it true that h_n<3^n for all integers less than or equal to k, so it will be true for k, k-1 and k-2, which is sufficient to prove it true for k+1, and so for all integers less than or equal to k+1. Which is exactly what you do with extented induction, indeed the principle of extended induction is provable from standard mathematical induction by a very similar method.

    Also you have to show that statement is true for first three integers.
    I say "Then the base case is .." My is exactly this and is proven exactly as in your proof.

    What I propose is in essense exactly the same as the other proof. It uses standard MI rather than EMI by changing the form of the stament that we are going to prove by induction, but the substance is identical.


    CB
    Last edited by CaptainBlack; February 26th 2009 at 11:36 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How close?
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 22nd 2010, 12:34 AM
  2. Is My Answer Close to Right? Cyclic Group Proof
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: December 10th 2009, 07:22 AM
  3. Definite Integral close??
    Posted in the Calculus Forum
    Replies: 6
    Last Post: November 22nd 2008, 05:09 PM
  4. Formal Modulus Proof: How close am I?
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: October 14th 2008, 05:07 PM
  5. Compact and Close Set
    Posted in the Calculus Forum
    Replies: 3
    Last Post: March 25th 2007, 04:50 AM

Search Tags


/mathhelpforum @mathhelpforum