Inequality with falling factorials

Question

in The Art of Computer Programming from Donald Knuth I came across the following inequality: \begin{equation} N^k - \binom{k}{2}N^{k-1} \leq N^{\underline{k}} \leq N^k. \end{equation} where $ N^{\underline{k}} = N(N-1)\ldots(N-k+1)$ is the falling factorial. I already showed the right inequality by induction. For the left inequality I also used induction with respect to $k \geq 1$ but I stuck at the induction step: Let $N \in \mathbb{N}$ and assume the inequality holds for $k \geq 1$. Then \begin{align} N^{k+1} - \binom{k+1}{2} N^{k} = N \left( N^k - (k+1)(k-2)\binom{k}{2}N^{k-1} \right) \end{align} what I got is \begin{equation} N \left( N^k - (k+1)(k-2)\binom{k}{2}N^{k-1} \right) \leq N N^{\underline{k}} \end{equation} and using the induction requirement and \begin{equation} N^{\underline{k}} = N^{\underline{k+1}} \frac{1}{N-k} \end{equation} for $N \neq k$ I got \begin{equation} N^{k+1} - \binom{k+1}{2} N^{k} \leq \frac{N}{N-k}N^{\underline{k+1}}. \end{equation} For $N < k$ this is clearly smaller than $N^{\underline{k+1}}$ but for $N > k$ I don't know how to proceed. Maybe the estimate is too rough, but I don't know how to estimate the factor $(k+1)(k-2) = k^2 - k - 2$ otherwise.

Answer 1

You can prove the left inequality by induction. You start with $k=1$, this should be easy to show. To prove the case $k \implies k+1$, you can multiply both sides of the inequality by $(N-k)$. This gives you the correct RHS. For the LHS:

\begin{align*} \left(N^k - \binom{k}{2}N^{k-1}\right)(N-k) &= N^{k-1}\left(N-\frac{k(k-1)}2\right)(N-k) \\ &=N^{k-1}\left(N^2-N\frac{k(k-1)}2-Nk+\frac{k^2(k-1)}2\right) \\ &=N^{k-1}\left(N^2-N\frac{k(k+1)}2+\frac{k^2(k-1)}2\right) \\ &\geq N^{k-1}\left(N^2-N\frac{k(k+1)}2\right) \\ &\geq N^k\left(N-\frac{k(k+1)}2\right) \\ \end{align*}

That should be enough to prove the relation.