Very loose bound on sum of first binomials

Question

Let $n\geq k\geq 2$. Is it always true that $$\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{k}\leq n^k?$$

The left-hand side is dominated by the term $\dfrac{n^k}{k!}$, so the statement should be true. But how can we show it rigorously?

Answer 1

The case $n=2$ can be verified easily. Also $k=2$ means that: $$ 1+n+\frac{n^2-n}{2}=\frac{n^2+n+2}{2}\leq n^2 $$ which is true for $n\geq 2$. So for the rest we assume $n,k\geq 3$. Now observe the following inequality for $1\leq i\leq n$: $$ \binom{n}{i}=\frac{n(n-1)\dots(n-i+1)}{i!}\leq n(n-1)^{i-1}. $$ Then we can use this inequality to bound the original sum:

\begin{align*} \binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{k}&\leq 1+n\sum_{i=1}^k(n-1)^{i-1}\\ &= 1+n\frac{(n-1)^{k}-1}{n-2}\\ &=\frac{n(n-1)^{k}-2}{n-2}\\ &\leq\frac{n(n-1)^{k}}{n-2}\\ &\leq n(n-1)^{k-2}(n+1)\\ &\leq n(n-1)^{k-3}n^2\\ &\leq n^{k}. \end{align*}