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

Question

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

Answer 1

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.

Answer 2

Observe that for $n \geq 100$,

\begin{align} (n+1)^2 & < \left(n+\frac{n}{40}\right)^2 \\ & = n^2+\frac{n^2}{20}+\frac{n^2}{1600} \\ & < n^2+\frac{n^2}{20}+\frac{n^2}{20} \\ & = n^2+\frac{n^2}{10} = n^2 \left(1+\frac{1}{10}\right) \end{align}

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.