5
$\begingroup$

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}$?

$\endgroup$
3
$\begingroup$

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.)

$\endgroup$
1
$\begingroup$

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}. $$

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.