# Prove that $\sum_{i=0}^d {n\choose i}\leq n^d +1$

Prove that $\sum_{i=0}^d {n\choose i}\leq n^d +1$

I tried doing it by induction. For $d=0$ the inequality says $1\leq 2$, so it's true.

For the induction step we assume $\sum_{i=0}^d {n\choose i}\leq n^d +1$ so we have $$\sum_{i=0}^{d+1} {n\choose i}\leq n^d +1 \leq n^d+1+ {n\choose {d+1}}$$ and this is where I am stuck. Why is $n^d+{n\choose {d+1}} \leq n^{d+1}$?

Hint: This is equivalent to

$${n \choose d+1} \leq n^{d+1}-n^d = n^d(n-1).$$

Now write

$${n \choose d+1} = \frac{n\cdot(n-1)\cdots(n-d)}{(d+1)!}.$$

Can you take it from here?

(Note: The inductive step you wish to prove is not true for $d=0$, so you should include $d=1$ as a separate base case.)

For $n\geq 2$ you can use $$n^d+1\underbrace{\leq}_{n^d\geq n\geq 1} n^d+n^d=2n^d\underbrace{\leq}_{n\geq 2}n\cdot n^d=n^{d+1}.$$

The LHS is the number of ways to choose either $0,1,\ldots,d$ out of $n$ without order and without repitition. The RHS is 1+ the number of ways to choose $d$ out of $n$ with order and repetition.

The +1 takes care of the $0$ choice in the LHS. Even without order in the RHS, it will be larger: given any choice of $k\leq d$, extend it to a choice of $d$ with repetition by adding elements you already chose. This construction is injective. Hence $LHS \leq RHS$.