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