1. ## Maths Induction

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.

2. Originally Posted by extatic
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.
Show p(4) is true, then assume p(k) is true, and then show p(k+1)

3. Hows this going?

n=4

2^4 ≥ n² and 2^4 < 4!
= 16 ≥ 16 and 16<24.

So this is correct.

now n = k.

2^k > k^2 and 2^k < k!

p(k+1)

2^k+1 > (k+1)² and 2^k+1 < (k+1)!

4. Originally Posted by extatic
Hows this going?

n=4

2^4 ≥ n² and 2^4 < 4!
= 16 ≥ 16 and 16<24.

So this is correct.

now n = k.

2^k > k^2 and 2^k < k!

p(k+1)

2^k+1 > (k+1)² \wedge 2^k+1 < (k+1)!
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

5. Originally Posted by extatic
Hows this going?

n=4

2^4 ≥ n² and 2^4 < 4!
= 16 ≥ 16 and 16<24.

So this is correct.

now n = k.

2^k > k^2 and 2^k < k!

p(k+1)

2^k+1 > (k+1)² and 2^k+1 < (k+1)!
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!$

6. Originally Posted by Archie Meade
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$<--You musn't do that. You must begin with $\displaystyle 2\cdot 2^k\ \ge\ 2\cdot k^2$

$\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!$<--You must not do that either. You must begin with $\displaystyle 2\cdot 2^k\ < 2\cdot k!$

$\displaystyle If\ 2^k\ <\ k!\ and\ if\ k\ >\ 1$

$\displaystyle 2^k\ <\ (k)k!$
You started your proof incorrectly where I marked in red. You are not to begin with the final results.

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

8. Originally Posted by novice
You started your proof incorrectly where I marked in red. You are not to begin with the final results.
Novice,

there was nothing wrong with the method.