Proof of a lemma with inequalities I read a paper about keyword search and just cannot understand the lemma.  Please help me to understand it, thanks.
Lemma 1: Let $v_1,v_2,\ldots,v_r$ be $r$ non-descending integers in the range from $1$ to $\lambda\ge 1$.  Gap-keeping requires at most $O(r\log(\lambda/r))$ bits to encode all of them.
Proof: Denote $u_1=v_i-v_{i-1}$ for $i\in[2,r]$, and $u_1=v_1$.  Note that $\{u_1,u_2,\ldots,u_r\}$ is exactly the set of values gap-keeping stores.  Each $u_1$ $(1\le i\le r)$ occupies $O(\log u_i)$ bits.  Hence, recording all of $u_1,u_2,\ldots,u_r$ requires at most
$$O(\log u_1+\log u_2+\ldots+\log u_r)=O\left(\log\left(\prod_{i=1}^ru_1\right)\right)\qquad(6)$$
bits.  A crucial observation is that
$$1\le u_1+u_2+\ldots+u_r\le\lambda$$
as all of $v_1,v_2,\ldots,v_r$ are between $1$ and $\lambda$.  Therefore, $\prod_{i=1}^ru_i$ is at most $(\lambda/r)^r$.  It thus follows that Equation 6 is bounded by $O(r\log(\lambda/r))$. $\square$
I can not understand why the product of $u_i$'s is at most $(\lambda/r)^r$.  Is there an inequality or formula about this?
 A: The product $\prod_{i=1}^r u_i$ is at a maximum when the $v_i$'s are as far apart as possible.  (If the $v_i$'s are close together, then their gaps $u_i$ would be smaller.)  The only way for the $v_i$'s to be as far apart as possible is if they are spaced $\frac{\lambda}{r}$ apart.  Thus, $\prod_{i=1}^r u_i$ is at most $\prod_{i=1}^r\frac{\lambda}{r}=\left(\frac{\lambda}{r}\right)^r$.
A: Given $\lambda$ and $r$, consider all possible combinations of $r$ integers that have a sum that does not exceed $\lambda$. What is the maximum possible product?
This maximum is attained when the sum is equal to $\lambda$: suppose otherwise, that $\sum_i u_i < \lambda$, where $\prod_i u_i$ is a maximum. Then just replace $u_1$ with $u_1+1$. This gives a sum that is $\le \lambda$, but a bigger product, contradiction.
So the question ends up being "given $r$ integers that sum to $\lambda$, what is the largest product attainable?" If the question involved $r$ real numbers instead of integers, then we see that the maximum happens when all of the $u_i$ equal $\lambda/r$, giving a product $(\lambda/r)^r$. So if we restrict the problem to its original state ($r$ integers instead of real numbers), the product cannot exceed $(\lambda/r)^r$, so it is still a valid upper bound.
