Page 1 of 2 12 LastLast
Results 1 to 15 of 25
Like Tree1Thanks

Math Help - mathematical induction

  1. #1
    Member tinspire's Avatar
    Joined
    Jul 2014
    From
    cali
    Posts
    104
    Thanks
    14

    mathematical induction

    I cannot get past this question. I'm stock on the induction step.$2^n>n^2$, $n \ge 5$.

    How to prove $S_{k+1}$?????
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,580
    Thanks
    1017

    Re: mathematical induction

    assuming $S_n$ is True.

    $2^{n+1} = 2\cdot 2^n > 2n^2$

    $(n+1)^2 = n^2 + 2n + 1$

    is $2n^2 > n^2 + 2n + 1$ ?

    $n^2 \overset{?}{>} 2n + 1$

    If you plot it you'll see this is true for $n>5$

    It's a simpler induction problem to prove it.

    If you can prove this you'll have shown that

    $2^{n+1} > (n+1)^2$ which is what you need to show for the original induction problem.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member tinspire's Avatar
    Joined
    Jul 2014
    From
    cali
    Posts
    104
    Thanks
    14

    Re: mathematical induction

    Thank you. I know I asked the question in a previous thread but I keep getting lost again
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member tinspire's Avatar
    Joined
    Jul 2014
    From
    cali
    Posts
    104
    Thanks
    14

    Re: mathematical induction

    Where did 2k^2 come from
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Feb 2014
    From
    United States
    Posts
    605
    Thanks
    307

    Re: mathematical induction

    $Let\ \mathbb X = {n \in \mathbb N\ such\ that\ n \ge 5\ and\ 2^n > n^2}.$ Note X may be the empty set.

    $2^5 = 32 > 25 = 5^2 \implies 5 \in \mathbb X.$ X is not the empty set.

    This proves that there is at least one member pf set X. We choose an arbitrary member of X called k.

    $\therefore \exists\ k \in \mathbb N,\ k \ge 5,\ and\ 2^k > k^2.$

    Now the most common way to proceed is to express the left hand and right hand sides of similar expressions in k + 1 in terms of expressions in k.

    $2^{(k+1)} = 2 * 2^k.$ Not hard.

    $(k + 1)^2 = k^2 + 2k + 1.$ Again not hard.

    Now comes the creative part of the proof.

    Hint: $2 * 2^k = 2^k + 2^k > k^2 + 2^k.$

    Can you complete the proof?

    Romsek beat me to it.
    Last edited by JeffM; July 23rd 2014 at 05:25 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jul 2014
    From
    Waterloo, ON
    Posts
    82
    Thanks
    18

    Re: mathematical induction

    I think I answered that before, in Discrete Math section of the forum? LoL.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member tinspire's Avatar
    Joined
    Jul 2014
    From
    cali
    Posts
    104
    Thanks
    14

    Re: mathematical induction

    @Denny I know, it was a good answer but I got confused about a few things.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member tinspire's Avatar
    Joined
    Jul 2014
    From
    cali
    Posts
    104
    Thanks
    14

    Re: mathematical induction

    this probably sound weird but I UNDERSTAND the idea. But how would i put it down on paper in a way that would make sense???
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Feb 2014
    From
    United States
    Posts
    605
    Thanks
    307

    Re: mathematical induction

    Quote Originally Posted by tinspire View Post
    this probably sound weird but I UNDERSTAND the idea. But how would i put it down on paper in a way that would make sense???
    Well, I may be biased, but I think post #5 is one way to put it down in a way that makes sense. That's just me of course.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member tinspire's Avatar
    Joined
    Jul 2014
    From
    cali
    Posts
    104
    Thanks
    14

    Re: mathematical induction

    do you think you can show me how to do the whole thing. like all the steps?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Feb 2014
    From
    United States
    Posts
    605
    Thanks
    307

    Re: mathematical induction

    Quote Originally Posted by tinspire View Post
    do you think you can show me how to do the whole thing. like all the steps?
    Actually, I think I did show all the steps up to a point, but I did not explain even those steps. My bad, but I was trying to get you to solve the problem, not do it for you.

    Quote Originally Posted by JeffM View Post
    $n \in set\ \mathbb X \implies n \in \mathbb N\ and\ n \ge 5\ and\ 2^n > n^2.$
    I have restated my first line to make it more exact. I am defining the set X as the set of all natural numbers > 4 for which what we want to prove is true. This is pure definition. At this point, X may be the empty set, meaning what we want to prove may not be true for any number.

    Quote Originally Posted by JeffM View Post
    $2^5 = 32 > 25 = 5^2 \implies 5 \in \mathbb X.$
    Now clearly 5 is a natural number > 4 and what we want to prove is true for 5. So 5 is in set X, and set X is NOT the empty set. With me to here?

    Now what I do is pick an ARBITRARY member of X and call it k. Because k is a member of X, it is true by the definition of X that

    Quote Originally Posted by JeffM View Post
    $k \in \mathbb N,\ k \ge 5,\ and\ 2^k > k^2.$
    Now what I need to do next is to show that $(k + 1) \in \mathbb N,\ (k + 1) \ge 5,\ and\ 2^{(k + 1)} > (k + 1)^2.$

    If I can show those three things, then k + 1 is a also member of X by the definition of X. Now it is trivial that if k > 4, then k + 1 > 5 > 4, and if k is a natural number then so is k + 1. So no one bothers to show these obvious conclusions explicitly, but they are there implicitly.

    Where the hard part of the proof comes in is showing that $2^{(k + 1)} > (k + 1)^2.$

    Now this may take creativity. There is no fixed procedure for finding a proof. BUT in proofs by weak mathematical induction, restating the components of what you want to prove in terms of k is usually necessary. So let's do that.

    Quote Originally Posted by JeffM View Post
    $2^{(k+1)} = 2 * 2^k.$ Not hard.

    $k^2 + 2k + 1 = (k + 1)^2.$ Again not hard.
    We are not fussing with k + 1 any longer.

    $2^{(k+1)} = 2 * 2^k = 2^ k + 2^k.$ This took a tiny smidgen of creativity.

    Now we already know that $2^k > k^2.$ How do we know that?

    A tiny bit more creativity is required. We need a lemma, namely $2^k \ge 2k + 1.$

    That lemma is in fact provable, and when we present the proof, we must put the proof of the lemma first. But for now I am just going to assume it is true,

    $2^k > k^2\ and\ 2^k \ge 2k + 1 \implies 2^k + 2^k > k^2 + 2k + 1 \implies 2 * 2^k > (k + 1)^2 \implies 2^{(k+1)} > (k + 1)^2.$

    But that is exactly what needed to be proved.

    So $\mathbb X = \mathbb N - \{0,\ 1,\ 2,\ 3,\ 4\} \implies$

    $n \in \mathbb N,\ and\ n \ge 5 \implies 2^n > n^2.$

    Now all that needs to be done is to prove the lemma (which can be done by weak mathematical induction) that

    $n \in \mathbb N,\ and\ n \ge 5 \implies 2^n > 2n + 1.$

    Now see if you can do prove the lemma by induction. The way you would present it is to show the proof of the lemma first. I am trying to show you how to find the proof, not how to present it.
    Last edited by JeffM; July 26th 2014 at 08:19 PM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member tinspire's Avatar
    Joined
    Jul 2014
    From
    cali
    Posts
    104
    Thanks
    14

    Re: mathematical induction

    its not something we're being tested on or that im ever gonna use again. my instructor just wanted us to do a few like on the side just for the sake of it :/ i dont really care that much about learning it properly
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member tinspire's Avatar
    Joined
    Jul 2014
    From
    cali
    Posts
    104
    Thanks
    14

    Re: mathematical induction

    ok the so the part im really confused on is proving the lemma (idk what that means) $2^n>2n+1$
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Feb 2014
    From
    United States
    Posts
    605
    Thanks
    307

    Re: mathematical induction

    Quote Originally Posted by tinspire View Post
    its not something we're being tested on or that im ever gonna use again. my instructor just wanted us to do a few like on the side just for the sake of it :/ i dont really care that much about learning it properly
    Well if you do not really care, there is absolutely no reason for me to care either.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member tinspire's Avatar
    Joined
    Jul 2014
    From
    cali
    Posts
    104
    Thanks
    14

    Re: mathematical induction

    i care about learning it enough to DO this problem but i dont care about getting the concepts engraved in my brain like i would for the other topics.

    your right though. im sorry dumb mathematical induction problem that's driving me nuts, i love you.
    Last edited by tinspire; July 26th 2014 at 09:53 PM.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Mathematical Induction help!!
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: May 10th 2013, 01:48 AM
  2. Mathematical induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 29th 2012, 03:23 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. Mat 111: mathematical induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 12th 2009, 09:16 AM
  5. Mathematical induction
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 20th 2008, 03:40 AM

Search Tags


/mathhelpforum @mathhelpforum