Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove by induction

  1. Nov 11, 2005 #1
    We've got the following to prove by induction:
    a) [itex]2n+1\le{2^n}[/itex]
    b) [itex]n^2\le{2^n}[/itex]
    (It is assumed that 0 is a natural number)

    a) This inequality is not valid for [itex]n=1,2[/itex], so to prove the inequality one has to show its validity for all [itex]n\ge{3}[/itex]:
    1) [itex]A(3):7\le{8}[/itex] (true)
    2) Assume that [itex]A(n)[/itex] is true.
    [itex]A(n+1): 2(n+1)+1\le{2^{n+1}}[/itex]
    [itex]2(n+1)+1=(2n+1)+2\le{2^n+2}\le{2^{n+1}}[/itex], since for [itex]2^n+2\le{2^{n+1}}[/itex] we have [itex]n\ge{1}[/itex]

    Is there a difference if I make the induction step this way?:
    2)[itex]A(n+1): 2(2n+1)\le{2^{n+1}}[/itex], so to prove A(n) we must show that [itex]2n+3\le{4n+2}[/itex], which is also true for [itex]n\ge{1}[/itex]
    The thing that disturbs me is that if we assume 0 to be a natural number the last inequalities in 2) in both cases do not hold...but I think this case doesn't play a role since we are to prove it for n greater 3...does it?

    b) This inequality is invalid for all [itex]n=3[/itex], so to show that the inequality is valid we must show that it is valid for all [itex]n\ge{4}[/itex]
    1) [itex]A(4)=16\le{16}[/itex] (true)
    2) Assume that [itex]A(n)[/itex] is true.
    [itex]A(n+1): (n+1)^2\le{2^{n+1}}[/itex]
    [itex](n+1)^2=n^2+2n+1\le{2^n+2n+1}\le{2^{n+1}}[/itex]. The last inequality in this string is equivalent to [itex]2n+1\le{2^n}[/itex], which was proved in a).

    Here, equally, the same question...Is there a difference if I do it this way?:
    2) [itex]A(n+1): 2n^2\le{2^{n+1}}[/itex]
    Last edited: Nov 11, 2005
  2. jcsd
  3. Nov 11, 2005 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I answered this on scienceforums.net

    but, you need to work on your method of proof and its exposition. it is not clear at all what you think you have shown and why that proves the result.

    2. can be done if we can show (n+1)^2 <2n^2 for then (n+1)^2 <2n^2 < 2.2^n (inductively) =2^(n+1)

    so prove that (n+1)^2 <2n^2 for all n sufficiently large.
  4. Nov 11, 2005 #3

    What about this inequality?
    1) A(0): 1<3 (true);
    2) Given A(n) then A(n+1):
    So to prove it we must show that [itex]\frac{1}{3(n+1)!}<1[/itex], which is straightforward because [itex]3(n+1)!>1[/itex] for all n, and at the same time [itex]\sum_{k=0}^{n}\frac{1}{k!}>\frac{1}{(n+1)!}[/itex]. The last inequality is pretty clear but how to prove it? Is it because of the fact that [itex]2(n+1)!>1[/itex] and [itex]\frac{(n+1)!}{n!}\ge{1}[/itex], so that [itex]\sum_{k=0}^{n}\frac{1}{k!}>{\frac{1}{(n+1)!}
    \Leftrightarrow{2(n+1)!+\sum_{k=2}^{n}\frac{(k+1)!}{k!}>1}[/itex] for all n?
    I'm not sure whether it is enough.
    Last edited: Nov 11, 2005
  5. Nov 11, 2005 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    again you're starting from the answer you want to prove this is bad.

    no, that will not suffice to prove it, and doesn't help.

    In anycase, this can be done easily without induction (i don't even see an obvious inductive proof) since


    is strictly bounded above by


    where you should make the ... into a series you can easily sum

    oh, may be i do see an inductive proof. start with the expression for the sum to n+1 (and DO NOT say it is less than 3) and manipulate it
    Last edited: Nov 11, 2005
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook