Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|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
add comment

2 Answers

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|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
add comment

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

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

Your Answer

 
discard

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.