Tell me more ×
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.
up vote 0 down vote favorite
1

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 at 21:29

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 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 at 23:57
up vote 0 down vote

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 at 19:18

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.