Exercise of induction with logarithm

Question

How to prove by induction that for all $n\in\mathbb{N},\,\,\, n\geq 6$ $$\displaystyle{20+n\log_2 n\leq n^2}$$

Language note, you don't prove "for induction," but rather "by induction." — Thomas Andrews, Mar 11 '13 at 19:39
What have you tried so far? Does the case $n=5$ hold? What if $20+k\log_2 k\leq k^2$? Can you obtain something to show it implies $20+k\log_2 (k+1)+\log_2(k+1)\leq k^2+2k+1$? — Pedro, Mar 11 '13 at 19:40
Peter tried to prove inequality without logarithms but I could not — Roiner Segura Cubero, Mar 11 '13 at 19:47

score 3 · Accepted Answer · answered Mar 11 '13 at 19:53

HINT: For your induction step you want to assume that $20+n\lg n\le n^2$ for some $n\ge 6$ and show that $20+(n+1)\lg(n+1)\le(n+1)^2$, where $\lg x=\log_2x$. One way to approach this is to see how much each side of the inequality increases: compare $(n+1)\lg(n+1)-n\lg n$ and $(n+1)^2-n^2$. If you can show that

$$(n+1)\lg(n+1)-n\lg n\le(n+1)^2-n^2\;,$$

you’ll be able to add that inequality to the induction hypothesis $20+n\lg n\le n^2$ to get the desired result.

Now $(n+1)^2-n^2=2n+1$, and

$$\begin{align*} (n+1)\lg(n+1)-n\lg n&=n\Big(\lg(n+1)-\lg n\Big)+\lg(n+1)\\ &=n\lg\frac{n+1}n+\lg(n+1)\\ &=n\lg\left(1+\frac1n\right)+\lg(n+1)\;, \end{align*}$$

so you want to show that

$$n\lg\left(1+\frac1n\right)+\lg(n+1)\le 2n+1$$

for $n\ge 6$. Now $\lg\left(1+\frac1n\right)<\frac12$ if $n\ge 3$ (why?) so for $n\ge 6$ we certainly have

$$n\lg\left(1+\frac1n\right)+\lg(n+1)\le\frac12n+\lg(n+1)\;;$$

can you show that $\lg(n+1)\le\frac32n+1$?

Exercise of induction with logarithm

1 Answers1