Results 1 to 8 of 8

Math Help - Does this inductive proof make sense?

  1. #1
    Member
    Joined
    Jul 2011
    Posts
    196

    Does this inductive proof make sense?

    I'm trying to prove by way of induction that:

    n! > 2^n for n \geq 4

    The base case is obviously true as 24 > 16
    I then took the inductive step and came up with the following:

    (k + 1)! > 2^{k+1}

    = (k + 1)*k! > 2*2^k

    I then figured that if k! > 2^k (assumption), then if the amount that the LFH is being multiplied by each time is > the amount that the RHS is being multiplied by each time, then the LHS must always be > RHS and the statement is true.

    So if:

    (k + 1) > 2

    then the original statement is true.

    Since n \geq 4 then the LHS multiple is always > 4 which is > 2 (RHS multiple), therefore the LHS is always greater than the RHS and the statement is true.

    Is this a valid proof? What are some other ways I could prove this?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Does this inductive proof make sense?

    Quote Originally Posted by terrorsquid View Post
    Is this a valid proof?
    Yes.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Does this inductive proof make sense?

    Quote Originally Posted by alexmahone View Post
    Yes.
    Is it an inductive proof because I took the inductive step? I thought that I had to show how to go to the next step in the chain from an arbitrary point to prove it via induction as opposed to just using general logic like I did above?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Does this inductive proof make sense?

    Without induction.






    Lemma:

    \sum _{n=1}^{\infty}\frac{2^n}{n!}<\infty

    Proof:

    We use, d'Alembert limit test.

    a_n=\frac{2^n}{n!}

    \lim_{n\to\infty}\frac{a_{n+1}}{a_n}=\lim_{n \to \infty } \frac{\frac{2^{n+1}}{(n+1)!}}{\frac{2^n}{n!}}=\lim  _{n\to\infty}\frac{2}{n+1}=0<1

    Hence, \sum _{n=1}^{\infty}\frac{2^n}{n!}<\infty.


    From lemma 1:

    \lim_{n\to\infty}\frac{2^n}{n!}=0

    hence, by limit definition, there exist n_0\in\mathbb{N}, such that for all n>n_0

    \left|\frac{2^n}{n!}\right|<1, n_0=5
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Does this inductive proof make sense?

    You have the right idea, but should not have written at the start

    (k+1)! > 2^(k+1)

    That is what you want to PROVE, so don't state it first as if it's already been proven.

    Rather, you could write it this way:

    Suppose (as the inductive hypotheis) k! > 2^k.

    And k+1 > 2.

    So, by monotonicity, (k+1)! = (k+1)k! > 2(2^k) = 2^(k+1).
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Does this inductive proof make sense?

    Quote Originally Posted by MoeBlee View Post
    You have the right idea, but should not have written at the start

    (k+1)! > 2^(k+1)

    That is what you want to PROVE, so don't state it first as if it's already been proven.

    Rather, you could write it this way:

    Suppose (as the inductive hypotheis) k! > 2^k.

    And k+1 > 2.

    So, by monotonicity, (k+1)! = (k+1)k! > 2(2^k) = 2^(k+1).
    Ok, thanks. That makes sense, I guess I was just trying to show my thought process of how I got to the proof by writing it out like that.

    I have another example and I didn't quite understand the steps given in the notes so I tried to apply a similar method to the new statement; I was wondering if it was also valid and if I post the notes that maybe someone could understand these notes.

    Show 2^n \geq n^2 for n \geq 4

    My proof:

    Base case is true.

    Induction step = assume 2^n \geq n^2 and test whether 2^{n+1} \geq (n+1)^2

    Similar to my other proof, given my assumption, if the change in the LFH >= the change in the RHS then the statement must be true, i.e., if

    2^n \geq 2n + 1

    then the statement is true. Since n \geq 4 the LHS >= 16 > 9 (RHS), the statement is true. Although I don't feel like I have PROVEN it for all changes in each side.


    Notes I have on this:

    2^{n+1} \geq 2*2^n \geq 2n^2 = n^2 + nn \geq n^2 +4n = n^2 + 2n + 2n \geq n^2 + 2n +1 = (n+1)^2

    Hence T(n) implies T(n+1)

    I didn't understand the step to n^2 + 4n.

    Sorry if I made some mistakes above, posting this in between classes - rushing.

    Thanks.
    Last edited by terrorsquid; August 10th 2011 at 07:49 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Does this inductive proof make sense?

    Quote Originally Posted by terrorsquid View Post
    I was just trying to show my thought process
    When you want to mention various objectives in the proof, use a word like 'show'.

    For example:

    Show that if k>=4 then k! > k^2.
    By induction on k:
    Base case. 4! > 4^2.
    Induction hypothesis: k! > k^2.
    Show that (k+1)! > 2^(k+1).
    etc...

    So, always make clear to the reader whether a formula is something you WANT to show as opposed to something you HAVE shown. If you mention a formula without such qualification, the reader should be allowed to take it that the formula is something that has already been proven, either previously in the subject or in your own proof.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Apr 2013
    From
    dfdsfdsf
    Posts
    2

    Re: Does this inductive proof make sense?

    Without induction.


    _______________________
    The Leverage Season 5 DVD crew helps a veteran hockey player who thinks team management!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Does this make sense?
    Posted in the Calculus Forum
    Replies: 2
    Last Post: April 4th 2011, 02:20 PM
  2. This does not make sense
    Posted in the Algebra Forum
    Replies: 3
    Last Post: November 11th 2008, 01:23 PM
  3. Does this Make sense?
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 22nd 2008, 03:11 PM
  4. Make Sense??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: July 31st 2008, 10:06 PM
  5. Does this proof make sense, probably wrong...
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 13th 2008, 10:03 PM

Search Tags


/mathhelpforum @mathhelpforum