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

Printable View

- Mar 17th 2009, 12:45 AMnoobonastickMathematical 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

- Mar 17th 2009, 01:34 AMADARSH
All the questions are almost same try them after seeing this

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

**First step:**

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

Now 7 >0 hence its correct for n = 5

**Assumption :**P(k) is correct

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

Hence$\displaystyle 2^k> k^2 $

**Proof for P(k+1) using assumption:**

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

since $\displaystyle 2^k > k^2 $

Hence

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

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

$\displaystyle 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 - Mar 17th 2009, 02:00 AMnoobonastick
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? - Mar 17th 2009, 03:35 AMADARSH
- Apr 8th 2010, 12:17 PMdaniel
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" ? - Apr 8th 2010, 12:40 PMArchie Meade
$\displaystyle 2^n-n^2\ >0$

is the same as

$\displaystyle 2^n>n^2$

Here is another way to prove it by induction..

**P(k)**

$\displaystyle 2^k>k^2$ for k>4

**P(k+1)**

Try to prove that

$\displaystyle 2^k>k^2$

causes

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

**Proof**

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

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

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

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

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

then

$\displaystyle 2^k+2^k>k^2+2k+1$ - Apr 8th 2010, 12:58 PMArchie Meade
For the 3rd..

**P(k)**

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

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

**P(k+1)**

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

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

**Proof**

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

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

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

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

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

Finally show P(k) it is valid for k=2 - Apr 9th 2010, 07:35 AMnovice
When we prove by Principle of Mathematical Induction, as much as it is possible, we want it be more convincing. Since the theorem says

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

It is more convincing to begin with $\displaystyle P(k)$ and end with $\displaystyle 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

$\displaystyle \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 $\displaystyle (k+1)^2$, and we arrive at

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

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

Notice that the first line of proof was $\displaystyle 2^k-k^2$

and the last line of proof is $\displaystyle 2^{k+1}-(k+1)^2>0$.

That is to say we have proved

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