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

  • $\begingroup$ 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. $\endgroup$ – JMoravitz Oct 5 '15 at 20:37
  • $\begingroup$ In my opinion, the hardest thing here is proving that $100^2 \le 1.1^n$. $\endgroup$ – TonyK Oct 5 '15 at 20:47
  • 1
    $\begingroup$ @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$. $\endgroup$ – Brian Tung Oct 5 '15 at 21:48

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.

  • $\begingroup$ Not such a loose condition, I would say. It fails for $n=95$. $\endgroup$ – TonyK Oct 5 '15 at 20:49
  • $\begingroup$ @TonyK: Not the overall proposition, just the induction step. $\endgroup$ – Brian Tung Oct 5 '15 at 20:51

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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