1. ## 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}$?????

2. ## 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.

3. ## Re: mathematical induction

Thank you. I know I asked the question in a previous thread but I keep getting lost again

4. ## Re: mathematical induction

Where did 2k^2 come from

5. ## 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.

6. ## Re: mathematical induction

I think I answered that before, in Discrete Math section of the forum? LoL.

7. ## Re: mathematical induction

@Denny I know, it was a good answer but I got confused about a few things.

8. ## 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???

9. ## Re: mathematical induction

Originally Posted by tinspire
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.

10. ## Re: mathematical induction

do you think you can show me how to do the whole thing. like all the steps?

11. ## Re: mathematical induction

Originally Posted by tinspire
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.

Originally Posted by JeffM
$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.

Originally Posted by JeffM
$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

Originally Posted by JeffM
$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.

Originally Posted by JeffM
$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.

12. ## 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

13. ## Re: mathematical induction

ok the so the part im really confused on is proving the lemma (idk what that means) $2^n>2n+1$

14. ## Re: mathematical induction

Originally Posted by tinspire
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.

15. ## 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.

Page 1 of 2 12 Last