Simple upper bound of sum of first m combinations

Question

There is a proof online which uses the following:

$$1 + n + {n\choose 2} + \ldots + {n \choose m} \leq n^m \quad \text{for } n,m\geq 2$$

Is there a name of this bound? Or a short proof anywhere? The ones given here are more 'advanced' since I believe this one is really loose.

The step is used at section 2.3 of this file.

Base case is easy. For the induction step, what can we do?
if this holds for $m-1$, then we need to prove $n^m - {n \choose m} \geq n^{m-1}$, right? does it follow easily? — independentvariable, Apr 26 '19 at 15:15

score 1 · Accepted Answer · answered Apr 26 '19 at 15:49

1

Hint: Following from your comment, $${n \choose m} =\frac{n!}{m!(n-m)!}=\frac{n(n-1)\cdots(n-m+1)}{m(m-1)\cdots1}.$$ We can assume that $m \ge n/2$ (just for the next step!) (otherwise consider ${n \choose n-m}$) and when this is the case $${n \choose m} = \frac{n(n-1)\cdots(n-m+1)}{m(m-1)\cdots1} = \frac{n}{m} \cdot \frac{(n-1)\cdots(n-m+1)}{(m-1)\cdots1} \le 2 n^{m-1}.$$ This gives $$n^{m-1} + {n\choose m} \le 3n^{m-1}$$ and so the conclusion holds for $n \ge 3$. It's easy to check the $n=2$ case.

Hope this helps!

answered Apr 26 '19 at 15:49

Zestylemonzi

4,103

Thank you so much! One last question, how does this work: $$\frac{n}{m} \cdot \frac{(n-1)\cdots(n-m+1)}{(m-1)\cdots1} \le 2 n^{m-1}.$$ – independentvariable Apr 26 '19 at 17:12
1

$n/m \le 2$ by our assumption and for the other term there are $m-1$ terms in the numerator and each is less than $n$. – Zestylemonzi Apr 26 '19 at 17:14
oh, that's very loose! But works :) Thanks so much! – independentvariable Apr 26 '19 at 17:16
No worries, glad to have helped :) – Zestylemonzi Apr 26 '19 at 17:31

Simple upper bound of sum of first m combinations

1 Answers1