Solving $\sum_{i=1}^n \log\frac{N}{x_i}$ where $\sum_{i=1}^n x_i = N$?

Question

The author of this paper gave this sum $\sum_{i=1}^n \log\frac{N}{x_i} = O(N)$, where $x_i, i = 1,\dots,n$ is a partition of $N$, but I cannot figure out how the summation is solved.

Answer 1

We have $$\sum_{i=1}^{n} \log \frac {N}{x_i}$$ $$=(\log N - \log x_1) +(\log N- \log x_2) +\cdots + (\log N -\log x_n) $$ $$= n (\log N) -(\log x_1 +\log x_2 +\cdots \log x_n) $$ $$=n\log N -\log \prod_{i=1}^{n} x_i $$

I think there is a typo in your question in the sense that $\prod_{i=1}^{n} x_i = N $. Hope it helps.

Answer 2

I'm honestly not sure about my proof but I will try. We will do an induction on $n$.

Starting at $n=1$, clearly $x_1 = N$ and the sum is $0$ which is $O(N)$.

Now assuming it is true up to $n$ and let's see $n+1$ : $$ \sum_{i=1}^{n+1} \log\frac{N}{x_i} = \sum_{i=1}^{n} \log\frac{N}{x_i} + \log \frac{N}{x_{n+1}}. $$ Now we know that for a fixed $N$, $\log \frac{N}{x_{n+1}} \leq \log N$ since $x_{n+1} \geq 1$. Therefore applying the induction hypothesis we get $$ \sum_{i=1}^{n+1} \log\frac{N}{x_i} = \sum_{i=1}^{n} \log\frac{N}{x_i} + \log \frac{N}{x_{n+1}} \leq O(N) + \log N = O(N) $$

Note also that this proof assumes nothing about $N$ (except $N \geq 1$) so this holds for all fixed $N$.