1. ## Mathematical Induction [inequalities]

Im not good at induction involving inequalities; can someone help me prove by mathematical induction:

1) 2^n - n^2 > 0 where n>4

2) n^2 - 3n + 2
≥ 0

3) 4^n - 1 - 7n
≥ 0 where n ≥2

thanks

2. Originally Posted by noobonastick
Im not good at induction involving inequalities; can someone help me prove by mathematical induction:

1) 2^n - n^2 > 0 where n>4

2) n^2 - 3n + 2
≥ 0

3) 4^n - 1 - 7n
≥ 0 where n ≥2

thanks

All the questions are almost same try them after seeing this

P(n) :2^n - n^2 >0 When n>4

First step:

$P(5) = 2^5 - 5^2 = 32 - 25 = 7$

Now 7 >0 hence its correct for n = 5

Assumption : P(k) is correct

ie; $2^k - k^2 >0$

Hence $2^k> k^2$

Proof for P(k+1) using assumption:

$2^{k+1}- (k+1)^2 = 2 \times 2^k - k^2 -1-2k$

since $2^k > k^2$
Hence

$2 \times 2^k - k^2 -1-2k > 2 \times k^2 - k^2 -1-2k$

$2 \times 2^k - k^2 -1-2k > k^2 -1-2k$

$2 \times 2^k - k^2 -1-2k > (k+1)^2$

But since (k+1)^2 is always a positive number (greater than 16 atleast ) thus proved that its correct for k+1 hence through the principle of mathematical induction this is proved

3. I can't seem to get the answer to the last question.

I have to prove 21k - 4 > 0 ... but how do I do that.

Do I state that if I sub in k ≥ 2, then 21k - 4> 0?

4. Originally Posted by noobonastick
I can't seem to get the answer to the last question.

I have to prove 21k - 4 > 0 ... but how do I do that.

Do I state that if I sub in k ≥ 2, then 21k - 4> 0?
Yes that is a good reason

5. I know the rules state create a new thread for each problem, but this isn't really a new problem. Rather, it's a question regarding the solution posted, as I'm unsure as well about the application of induction to inequalities.

Reading the Assumption step, I'm not sure how that would work if p(n) = 2^n > n^2, for n>4. Would it essentially be the opposite to what was posted, becoming "hence: 2^n - n^2 > 0" ?

6. $2^n-n^2\ >0$

is the same as

$2^n>n^2$

Here is another way to prove it by induction..

P(k)

$2^k>k^2$ for k>4

P(k+1)

Try to prove that

$2^k>k^2$

causes

$2^{k+1}>(k+1)^2$

Proof

$2^{k+1}>(k+1)^2$ ?

$(2)2^k>k^2+2k+1$ ?

$2^k+2^k>k^2+2k+1$ ?

If k>4, then $2^k>2k+1$

hence, if $2^k>k^2$

then

$2^k+2^k>k^2+2k+1$

7. For the 3rd..

P(k)

$4^k-1-7k\ \ge\ 0,\ k\ \ge\ 2$ ?

$4^k\ \ge\ 7k+1$ ?

P(k+1)

Does $4^k\ \ge\ 7k+1$ cause

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

Proof

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

$(4)4^k\ \ge\ 7k+1+7$ ?

$4^k+(3)4^k\ \ge\ 7k+1+7$ ?

If $4^k\ \ge\ 7k+1$

then $(3)4^k$ is definately greater than 7.

Finally show P(k) it is valid for k=2

Assumption : P(k) is correct

ie; $2^k - k^2 >0$

Hence $2^k> k^2$

Proof for P(k+1) using assumption:

$2^{k+1}- (k+1)^2 = 2 \times 2^k - k^2 -1-2k$

since $2^k > k^2$
Hence

$2 \times 2^k - k^2 -1-2k > 2 \times k^2 - k^2 -1-2k$

$2 \times 2^k - k^2 -1-2k > k^2 -1-2k$

$2 \times 2^k - k^2 -1-2k > (k+1)^2$
When we prove by Principle of Mathematical Induction, as much as it is possible, we want it be more convincing. Since the theorem says

$P(k) \Rightarrow P(k+1)$

It is more convincing to begin with $P(k)$ and end with $P(k+1)$. By beginning with P(k+1) is less desirable though it is not always the case for Strong Principle of Mathematical Induction.

As much as we could, we would begin with

\begin{aligned}
2^k-k^2 &>0\\
2^k&>k^2 \text{. Now multiplying bothsides by 2, we obtain}\\
2^{k+1}&>2k^2=K^2+k^2\geq K^2+ 5k=k^2+2k+3k\geq k^2+2k+15>k^2+k+1\\
2^{k+1}&>k^2+k+1=(k+1)^2\\
2^{k+1}&>(k+1)^2\\
\end{aligned}
.

Now subtract both sides by $(k+1)^2$, and we arrive at

$2^{k+1}-(k+1)^2>0$, which is precisely as desired; namely, P(k+1).

$2^{k+1}-(k+1)^2>0$.

Notice that the first line of proof was $2^k-k^2$
and the last line of proof is $2^{k+1}-(k+1)^2>0$.

That is to say we have proved

$P(k) \Rightarrow P(k+1)$ for $\forall k >4, k\in \mathbb{N}$