Results 1 to 5 of 5

Math Help - proof by induction help

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    22

    proof by induction help

    I've been reviewing mathematical induction and I don't really get how to prove inequalities by induction. I've been working on this problem for a while..

    2^n\leq(n+1)!

    so far I've proved n=1 for the base, then I assume n=k.
    2^k\leq(k+1)!

    then, I use n=(k+1)..
    2^{k+1}\leq((k+1)+1)!

    this is where i get confused, I did this..
    2\ast(k+1)!=((k+1)+1)!
    I multiplied by 2 because you can rewrite 2^{k+1} as 2^k\ast2 but i'm not sure if multiplying by two on the other side is right since it's an inequality and not an equation like what i've been working with up until now. I would really appreciate help with trying to solve this
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    You can multiply both sides of an equation or an inequality by the same number, but your last equality is still wrong. However, it leads to the right idea.

    We know (by assumption) that 2^k <= (k + 1)!. How does one obtain 2^{k+1} from 2^k and (n + 2)! from (n + 1)! ? 2^{k+1} is obtained by multiplying 2^k by 2, so let's multiply both sides of 2^k <= (k + 1)! by 2. Then how does 2(k + 1)! compare with (k + 2)! ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    22
    ok, so instead of the last equation, i did this
    2(k+1)!\leq(k+2)!
    and i expanded the factorial things, but i'm not sure if this is the right way to do it.
    2((k+1)(k))\leq(k+2)(k+1)(k)
    then i divided by (k+1)(k) on both sides and got
    2<=(k+2)
    which seems like it would prove the inequality since you can't add k to 2 and get less than 2. Is this right?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    Basically, yes. In going from 2(k+1)!\leq(k+2)! to 2((k+1)(k))\leq(k+2)(k+1)(k) you not only expanded the factorials but also divided both sides of the first inequality by (k - 1)! since 2(k + 1)! = 2(k + 1)k(k - 1)!, not just 2(k + 1)k. You could divide both sides of the first inequality by (k + 1)! to get 2 <= k + 2.

    Also, it is important to watch the direction of the proof. Usually a finished proof is presented as a sequence of statements, each of which implies the following. However, in constructing a proof and especially in solving an equation or an inequality we tend to go the opposite way: start from what we need to prove and simplify it until we get to something clearly true. Strictly speaking, in the end we must reverse the direction.

    So here is how I would write the inductive step. Assume the induction hypothesis (IH), i.e., 2^k\le (k+1)! for some k\ge 0. We need to prove that 2^{k+1}\le(k+2)!.

    Multiplying both sides of the the IH by 2, we get

    2^{k+1}\le2(k+1)! (*)

    Also, 0\le k\Rightarrow 2\le k+2\Rightarrow 2(k+1)!\le(k+2)(k+1)!=(k+2)!. Combining this with (*), we get 2^{k+1}\le(k+2)!.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by yaykittyeee View Post
    I've been reviewing mathematical induction and I don't really get how to prove inequalities by induction. I've been working on this problem for a while..

    2^n\leq(n+1)!

    so far I've proved n=1 for the base, then I assume n=k.
    2^k\leq(k+1)!

    then, I use n=(k+1)..
    2^{k+1}\leq((k+1)+1)!

    this is where i get confused, I did this..
    2\ast(k+1)!=((k+1)+1)!
    I multiplied by 2 because you can rewrite 2^{k+1} as 2^k\ast2 but i'm not sure if multiplying by two on the other side is right since it's an inequality and not an equation like what i've been working with up until now. I would really appreciate help with trying to solve this
    Alternatively,

    "If" 2^k\le(k+1)!\Rightarrow\ (2)2^k\le(2)(k+1)!<(k+2)(k+1)!

    for k\ge\ 1

    and since (k+2)(k+1)!=(k+2)!=[(k+1)+1]!

    2^{k+1}\le(k+2)! "if" 2^k\le(k+1)!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by induction that 4| 5^n - 1
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 17th 2010, 10:23 AM
  2. proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 17th 2010, 07:11 AM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. induction proof
    Posted in the Algebra Forum
    Replies: 7
    Last Post: November 1st 2008, 04:32 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum