Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 3 down vote accepted

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}$$

share|cite|improve this answer
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
but on the left hand side
so that
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.)

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.