# Prove $n^2 \leq 1.1 ^{n}$ by induction

Prove that for all $n \geq 100$ you have $n^2 \leq 1.1^n$

Base Case:

$n = 100$

$(100)^2 \leq 1.1^{100}$ (True)

Inductive Case:

Suppose $(k-1)^2 \leq 1.1^{k-1}$ for some $k \geq 101$

Prove $k^2 \leq 1.1^k$

I know $1.1^k = 1.1^{k-1} \cdot 1.1$

So I have,

$1.1^{k-1} \cdot 1.1 \geq 1.1(k-1)^2$

I know i need to eventually get $k^2$ on the RHS but I'm stuck

• I made a few edits. Most of them were simply putting equations into $\LaTeX$, but note a few key changes in the phrasing. In particular, Suppose ... for all k>100 should be corrected to Suppose ... for some k>100. There is a big difference between the phrases for all and for some. – JMoravitz Oct 5 '15 at 20:37
• In my opinion, the hardest thing here is proving that $100^2 \le 1.1^n$. – TonyK Oct 5 '15 at 20:47
• @TonyK: Short of using log tables, I couldn't find a much easier way than to show, using the binomial theorem, that $(1+1/10)^{25} > 10$. The first five terms suffice, just barely: $1+25/10+300/100+2300/1000+12650/10000 = 100650/10000 = 10.065$. – Brian Tung Oct 5 '15 at 21:48

Observe that for $n \geq 100$,
Use that in the induction step and all should be well. Note that $n \geq 100$ is rather a loose condition for the induction step.
• Not such a loose condition, I would say. It fails for $n=95$. – TonyK Oct 5 '15 at 20:49
The simplest is maybe to note that it is equivalent to $2\log(n)\leq n\log(1.1)$ i.e. to $\frac{n}{\log(n)} \geq \frac2{\log(1.1)}$
The function $x\rightarrow \frac{x}{\log(x)}$ is increasing for x>100 (look at the derivative, it has the sign of $\log(x)-1$). So if you have the property for one $n$, you have it for all the next ones. Then, you only have to compute it for 100.