Hi Everyone,
Still trying to grasp doing inductions, saw this question today but i got it completely wrong.
Any assistance would be most appreciative.
Using induction to pove that for all n≥4 the inequalities 2ⁿ ≥ n² and 2ⁿ < n! hold.
Now, you have to prove it! For example, suppose $\displaystyle k\geq 4$ and P(k) is true. So
$\displaystyle 2^k \geq k^2 \wedge 2^k < k!$
Now consider $\displaystyle P(k+1)$
$\displaystyle LHS= 2^{k+1} \geq (k+1)^2$
By inductive hypothesis
$\displaystyle 2^k.2 \geq 2^k +2k+1$
$\displaystyle \geq (k+1)^2$
=RHS
P(k)
$\displaystyle 2^k\ \ge\ k^2\ ?$......$\displaystyle k\ \ge\ 4$
P(k+1)
$\displaystyle 2^{k+1}\ \ge\ (k+1)^2\ ?$.......$\displaystyle k\ \ge\ 4$
Proof
$\displaystyle 2^12^k\ \ge\ k^2+2k+1\ ?$......$\displaystyle k\ \ge\ 4$
by multiplying out $\displaystyle (k+1)^2$
We are showing whether or not P(k) being true causes P(k+1) to be true.
This is how induction works.
The comments in the next post "correcting" this are incorrect
$\displaystyle 2^k+2^k\ \ge\ k^2+2k+1\ ?$.......$\displaystyle k\ \ge\ 4$
If P(k) is true, then $\displaystyle 2^k\ \ge\ k^2$
therefore is $\displaystyle 2^k\ \ge\ 2k+1\ for\ k\ \ge\ 4\ ?$
$\displaystyle 2^4\ \ge\ 2(4)+1$
Therefore if $\displaystyle 2^k\ \ge\ k^2$
then $\displaystyle 2^{k+1}\ \ge\ (k+1)^2$ also.
P(k)
$\displaystyle 2^k\ <\ k!\ ?$
P(k+1)
$\displaystyle 2^{k+1}\ <\ (k+1)!\ ?$
Proof
$\displaystyle 2^12^k\ < (k+1)k!\ ?$
$\displaystyle 2^k+2^k\ < (k)k!+k!$
We are showing that P(k) being true causes P(k+1) to be true
$\displaystyle If\ 2^k\ <\ k!\ and\ if\ k\ >\ 1$
$\displaystyle 2^k\ <\ (k)k!$
The whole thing about basic mathematical induction is tedious algebra expansion and simplification. If you can expand one small step at a time, you should be able to do any form of induction in your first course of math in college. I am going to show you how to take the small steps. If you observe the example, you should not have trouble with simple induction.
Remark: You can break down you proof into two parts: One for $\displaystyle 2^n\geq n^2$, and the other one, $\displaystyle 2^n<n!$
You are to prove for all $\displaystyle n\geq 4, P \wedge Q$, where
$\displaystyle P: 2^n\geq n^2$ and $\displaystyle Q:2^n<n!$
Note: Keep this in mind that $\displaystyle n\geq 4$ (Let's call it the precondition.) We will return to this later.
Here we prove statement $\displaystyle P$:
Basis step:
For $\displaystyle n=4, P: 2^4\geq 4^2$. Since this is true, we move on.
Inductive Step:
Suppose for a positive integer $\displaystyle k> 4$ that $\displaystyle 2^k\geq k^2$ is true. Then multiplying through by 2, we obtain
$\displaystyle 2 \cdot k \geq 2\cdot k^2\\$. Observe each step:
$\displaystyle 2 \cdot k \geq k^2+ k^2\\$
$\displaystyle 2 \cdot k \geq k\cdot k+ k^2\\$ Next, we substitute the precondition for one of the $\displaystyle k's$
$\displaystyle 2 \cdot k \geq 4\cdot k+ k^2\\$
$\displaystyle 2 \cdot k \geq k^2 +2 k+2k \\$ Next, we substitute the precondition for the $\displaystyle k$ in the last term.
$\displaystyle 2 \cdot k \geq k^2 +2 k+2\cdot 4 >(k^2 +2 k+1)$ Therefore,
$\displaystyle 2 \cdot k \geq (k+1)^2$
Now, we will prove the statement $\displaystyle Q:$
Basis Step:
For all positive integer $\displaystyle n> 4$, $\displaystyle 16=2^4<4!=24$. This one checked.
Inductive Step:
Suppose for all positive integer $\displaystyle k\geq4, 2^k < k!$. Then multiplying through by 2, we obtain
$\displaystyle 2^k < 2k!$
$\displaystyle 2^k < (1+1)k!<(k+1)\cdot k!$ since the smallest $\displaystyle k$ in the parenthesis is greater than 4. Therefore,
$\displaystyle 2^k <<(k+1)!$
Consequently, for all positive integer $\displaystyle n \geq 4, P \wedge Q.$