# Prove by induction - can not prove the step case

I have to prove by induction the following:

$$\sum^{n-1}_{k=2} k\log_{10} k \le \frac{1}{2}n^2\log_{10} n-\frac{1}{8}n^2$$

I have proven the base case, but I am stuck at the step case. I have tried different ways but always have stuck somewhere and could not finish it.

Anyone has any idea?

Thank you

## 1 Answer

What you want to show is that $\sum^{n-1}_{k=2} k\log_{10} k \le \frac{1}{2}n^2\log_{10} n-\frac{1}{8}n^2$ implies $\sum^{n}_{k=2} k\log_{10} k \le \frac{1}{2}(n+1)^2\log_{10} (n+1)-\frac{1}{8}(n+1)^2$.

From your assumption,

$\begin{array}\\ \sum^{n}_{k=2} k\log_{10} k &=\sum^{n-1}_{k=2} k\log_{10} k+n\log_{10} n\\ &\le\frac{1}{2}n^2\log_{10} n-\frac{1}{8}n^2+n\log_{10} n\\ \end{array}$

Therefore, you have succeeded if you can prove $\frac{1}{2}n^2\log_{10} n-\frac{1}{8}n^2+n\log_{10} n \le \frac{1}{2}(n+1)^2\log_{10} (n+1)-\frac{1}{8}(n+1)^2$.

I will leave this up to you.

(Since you asked for help. here it is. Note that this is just algebra.)

You want to show that

$\begin{array}\\ 0 &\le \frac{1}{2}(n+1)^2\log (n+1)-\frac{1}{8}(n+1)^2 -\frac{1}{2}n^2\log n+\frac{1}{8}n^2+n\log n\\ &= \frac{1}{2}(n^2+2n+1)\log (n+1)-\frac{1}{8}(n^2+2n+1) -\frac{1}{2}n^2\log n-\frac{1}{8}n^2+n\log n\\ &= \frac{1}{2}n^2(\log (n+1)-\log (n))+\frac{1}{2}(2n+1)\log (n+1)-\frac{1}{8}(2n+1)+n\log n\\ &= \frac{1}{2}n^2(\log (n+1)-\log (n))+(n+\frac12)\log (n+1)-\frac{1}{8}(2n+1)+n\log n\\ &= \frac{1}{2}n^2(\log (n+1)-\log (n))+n(\log (n+1)+\log (n))+\frac12\log (n+1)-\frac{1}{8}(2n+1)\\ &= \frac{1}{2}n^2(\log (n+1)-\log (n))+n(\log (n+1)+\log (n)-\frac14)+\frac12\log (n+1)-\frac{1}{8}\\ \end{array}$

and all these terms are positive for $n \ge 2$.

• I had reached this far. This is where I am stuck. Could you tell me how to prove it? – zeeks Mar 10 '16 at 21:47
• Added a proof. You should check my algebra. – marty cohen Mar 10 '16 at 22:20