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:
$\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
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" ?
$\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$
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
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}$