1

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

lsf456
  • 43
  • 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 08 '13 at 21:29

2 Answers2

3

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 08 '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. –  Jan 08 '13 at 23:57
0

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.)

mol3574710n0fN074710n
  • 724