1

Note $\log$ is $\log_2$ in this problem.

I am working on the proof of a lemma that my professor used in class. He said we could verify that it works if we want, but I think I used the inductive hypothesis in such a way that I cannot continue my proof. Either that or I am missing a simple algebraic manipulation.

The use of my inductive hypothesis is based on the fact that I am dealing with inequalities, so $lg(n) \leq lg(n+1)$ for all $n$. Bellow is my work so far.

$\sum_{k=2}^{n-1}k\log k \leq \frac{1}{2}n^2 \log n - \frac{1}{8}n^2$

Base step: $2 \leq \frac{9}{2} \log 3 - \frac{9}{8}$

$2 \leq \frac{9}{2} \log 2 - \frac{9}{8} = \frac{27}{8} \leq \frac{9}{2} \log 3 - \frac{9}{8}$

Assume: $\sum_{k=2}^{n-1}k\log k \leq \frac{1}{2}n^2 \log n - \frac{1}{8}n^2$

Show: $\sum_{k=2}^{n}k\log k \leq \frac{1}{2}(n+1)^2 \log (n+1) - \frac{1}{8}(n+1)^2$

$\sum_{k=2}^{n-1}k\log k + n \log n \leq \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 \leq \frac{1}{2}(n+1)^2 \log (n+1) - \frac{1}{8}(n+1)^2$

$\require{cancel} \cancel{\frac{1}{2}n^2 \log n} - \cancel{\frac{1}{8}n^2} + n \log n \leq \cancel{\frac{1}{2}n^2 \log (n+1)} + n \log (n+1) + \frac{1}{2} \log (n+1) - \cancel{\frac{1}{8}n^2} - \frac{1}{4}n - \frac{1}{8}$

$n \log n \leq n \log (n+1) + \frac{1}{2} \log (n+1) - \frac{1}{4}n - \frac{1}{8}$

At this point I am not sure how to proceed.

Pareod
  • 351
  • People often don't want to try to read other people's handwriting here. Please visit this page for information on how to type with $\LaTeX$ and MathJax here. With enough practice, you can type math even faster than you can handwrite it and it is much easier to read. – JMoravitz Sep 04 '18 at 00:22
  • I replaced it with $\LaTeX$. – Pareod Sep 04 '18 at 00:46
  • You cancelled $\frac12n^2\log n$ with $\frac12n^2\log (n+1)$. – John Bentin Sep 04 '18 at 14:16

1 Answers1

1

If you draw some simple diagrams, given some $f(x) > 0$ and $f'(x) > 0,$ you find $$ \int_{a-1}^b f(x) dx < \sum_{k=a}^b f(k) < \int_{a}^{b+1} f(x) dx $$

enter image description here

You are using $a=2$ and $b=n-1$

This is especially helpful when we know a closed form indefinite integral of $f$

In particular, using logarithm base $e \approx 2.718,$ we have $$ \int x \log x \; \; dx = \left( \frac{2 x^2 \log x - x^2}{4} \right) + \mbox{constant} $$

NOT SURE: after your edit, I cannot tell which logarithm you are using.

I would say that the constant $2$ matters here, you are using $$ \frac{\log x}{\log 2} $$ and need to be a little careful about that:

$$ \int \frac{x \log x}{\log 2} \; \; dx = \left( \frac{2 x^2 \log x - x^2}{4 \log 2} \right) + \mbox{constant} $$

Will Jagy
  • 139,541