# mathematical induction with inequality

I am trying to prove by mathematical induction that $(k+3)^2 < 2^{k+3}$ for $k = 1, 2, \ldots$.

-
Let $m = k+4$. Then you are asked to show that $m^2 < 2^m$ when $m > 4$. This change of variables should avoid some of the mess. – JavaMan Jan 8 '13 at 21:29

From induction step, we have $$(n+4)^2 < 2^{n+4}$$ Now we need to prove that $$((n+1)+4)^2 < 2^{(n+1)+4}$$ First show that $$((n+1)+4)^2 \leq 2(n+4)^2$$ for all $n \in \mathbb{N}$. Once you have this make use of the fact that$$(n+4)^2 < 2^{n+4}$$ to conclude that $$((n+1)+4)^2\leq 2(n+4)^2 < 2 \cdot2^{n+4} = 2^{n+5}$$

-
Thanks! Where do you get 2(n+4)^2 from? I can't figure that part out, but the rest makes sense – lsf456 Jan 8 '13 at 20:07
@lsf456 You need to prove that fact i.e. you need to prove that $(n+5)^2 \leq 2(n+4)^2$ i.e. $n^2 + 10n + 25 \leq 2n^2 + 16n + 32$ i.e. $n^2 +6n + 7 \geq 0$, which I guess is trivial to prove. – user17762 Jan 8 '13 at 23:57

We have on the right hand side
$$2^{(k+1)+4}=2\cdot2^{k+4}$$
but on the left hand side
$$(k+1+4)^2=(k+4)^2+2\cdot(k+4)+1$$
so that
$$\frac{(k+1+4)^2}{(k+4)^2}=\frac{(k+4)^2+2\cdot(k+4)+1}{(k+4)^2}=1+\frac{2}{k+4}+\frac{1}{(k+4)^2}\leq1\frac{11}{25}<2$$
Thus, by comparing growth factors for the step from $k$ to $k+1$ you are done.

(As Inquisitive pointed out there was an error in the last line that I now corrected. However the relevant estimate $<2$ is unaffected.)

-
Wrong: If I give k=1 in your last equation ,that <= 6/5 not holding – Inquisitive Jan 8 '13 at 19:18