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


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$.

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

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.