# Induction hint

• February 6th 2008, 06:00 PM
powderteacher
Induction hint
Can someone give me a hint on this?
Prove: $
P(n):\,n^2 < 2^n \,$
for all
$n \in J$ where $n \geqslant 5$
Proof by induction
a. $P(5):\,\,5^2 < 2^5$
25<32 is true;
b. assume that P(k) is true for some $
k \geqslant 5$
$k \in J$
c. Show that P(k+1) is true
$
\begin{gathered}
(k + 1)^2 < 2^{k + 1} \hfill \\
(k + 1)(k + 1) < 2^k \cdot 2 \hfill \\
k^2 + 2k + 1 < 2^k \cdot (1 + 1) \hfill \\
k^2 + 2k + 1 < 2^k + 2^k \hfill \\
\end{gathered}$

Is the left-hand side less than the right-hand side because the degree of the right is bigger? If so how do I prove that?
Thanks for any hints