# Math Help - Maths Induction

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 $k\geq 4$ and P(k) is true. So

$2^k \geq k^2 \wedge 2^k < k!$

Now consider $P(k+1)$

$LHS= 2^{k+1} \geq (k+1)^2$

By inductive hypothesis

$2^k.2 \geq 2^k +2k+1$

$\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)

$2^k\ \ge\ k^2\ ?$...... $k\ \ge\ 4$

P(k+1)

$2^{k+1}\ \ge\ (k+1)^2\ ?$....... $k\ \ge\ 4$

Proof

$2^12^k\ \ge\ k^2+2k+1\ ?$...... $k\ \ge\ 4$

by multiplying out $(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

$2^k+2^k\ \ge\ k^2+2k+1\ ?$....... $k\ \ge\ 4$

If P(k) is true, then $2^k\ \ge\ k^2$

therefore is $2^k\ \ge\ 2k+1\ for\ k\ \ge\ 4\ ?$

$2^4\ \ge\ 2(4)+1$

Therefore if $2^k\ \ge\ k^2$

then $2^{k+1}\ \ge\ (k+1)^2$ also.

P(k)

$2^k\ <\ k!\ ?$

P(k+1)

$2^{k+1}\ <\ (k+1)!\ ?$

Proof

$2^12^k\ < (k+1)k!\ ?$

$2^k+2^k\ < (k)k!+k!$

We are showing that P(k) being true causes P(k+1) to be true

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

$2^k\ <\ (k)k!$

6. Originally Posted by Archie Meade
P(k)

$2^k\ \ge\ k^2\ ?$...... $k\ \ge\ 4$

P(k+1)

$2^{k+1}\ \ge\ (k+1)^2\ ?$....... $k\ \ge\ 4$

Proof

$2^12^k\ \ge\ k^2+2k+1\ ?$...... $k\ \ge\ 4$<--You musn't do that. You must begin with $2\cdot 2^k\ \ge\ 2\cdot k^2$

$2^k+2^k\ \ge\ k^2+2k+1\ ?$....... $k\ \ge\ 4$

If P(k) is true, then $2^k\ \ge\ k^2$

therefore is $2^k\ \ge\ 2k+1\ for\ k\ \ge\ 4\ ?$

$2^4\ \ge\ 2(4)+1$

Therefore if $2^k\ \ge\ k^2$

then $2^{k+1}\ \ge\ (k+1)^2$ also.

P(k)

$2^k\ <\ k!\ ?$

P(k+1)

$2^{k+1}\ <\ (k+1)!\ ?$

Proof

$2^12^k\ < (k+1)k!\ ?$

$2^k+2^k\ < (k)k!+k!$<--You must not do that either. You must begin with $2\cdot 2^k\ < 2\cdot k!$

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

$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 $2^n\geq n^2$, and the other one, $2^n

You are to prove for all $n\geq 4, P \wedge Q$, where

$P: 2^n\geq n^2$ and $Q:2^n

Note: Keep this in mind that $n\geq 4$ (Let's call it the precondition.) We will return to this later.

Here we prove statement
$P$:

Basis step:

For $n=4, P: 2^4\geq 4^2$. Since this is true, we move on.

Inductive Step:

Suppose for a positive integer $k> 4$ that $2^k\geq k^2$ is true. Then multiplying through by 2, we obtain

$2 \cdot k \geq 2\cdot k^2\\$. Observe each step:
$2 \cdot k \geq k^2+ k^2\\$
$2 \cdot k \geq k\cdot k+ k^2\\$ Next, we substitute the precondition for one of the $k's$
$2 \cdot k \geq 4\cdot k+ k^2\\$
$2 \cdot k \geq k^2 +2 k+2k \\$ Next, we substitute the precondition for the $k$ in the last term.
$2 \cdot k \geq k^2 +2 k+2\cdot 4 >(k^2 +2 k+1)$ Therefore,
$2 \cdot k \geq (k+1)^2$

Now, we will prove the statement $Q:$

Basis Step:

For all positive integer $n> 4$, $16=2^4<4!=24$. This one checked.

Inductive Step:

Suppose for all positive integer $k\geq4, 2^k < k!$. Then multiplying through by 2, we obtain

$2^k < 2k!$
$2^k < (1+1)k!<(k+1)\cdot k!$ since the smallest $k$ in the parenthesis is greater than 4. Therefore,
$2^k <<(k+1)!$

Consequently, for all positive integer $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.