1
$\begingroup$

I am trying to prove the following bound using induction (where N>D):

$\sum_{i=0}^{D}\binom{N}{i} \leq N^{D} + 1$

I would appreciate any help on how to prove this. Thanks.

Currently I have looked at low values of D (base cases) but I don't understand how to formulate an induction step without using any prior information on the final result.

D=0: $\sum_{i=0}^{0}\binom{N}{i} \leq N^{0} + 1 \Leftrightarrow 1 \leq 2$

D=1: $\sum_{i=0}^{1}\binom{N}{i} \leq N^{1} + 1 \Leftrightarrow N + 1 \leq N + 1$

D=2: $\sum_{i=0}^{2}\binom{N}{i} \leq N^{2} + 1 \Leftrightarrow \frac{N^{2}}{2} + \frac{N}{2} + 1 \leq \frac{N^{2}}{2} + \frac{N^{2}}{2} + 1 \leq N^{2} + 1$

Maybe a first step in solving this is:

$\sum_{i=0}^{D}\binom{N}{i} = \sum_{i=0}^{D-1}\binom{N}{i} + \binom{N}{D}$ ??

$\endgroup$
  • $\begingroup$ I edited the post to show what I have tried. Do you have any suggestions on how to formulate an induction step? $\endgroup$ – ahmad1374 Feb 14 '17 at 4:00
  • $\begingroup$ You are allowed to use the prior information for the D case to prove D+1. $\endgroup$ – Q the Platypus Feb 14 '17 at 5:20
0
$\begingroup$

Possible Solution Route?


I'll change notation because I like using $a,n$ more $$1+ a^n \ge \sum_{k=0}^n {a \choose k} \tag{1}$$ Assuming you have your base case, we assume $(1)$. We now have that $$1+(a+1)^n$$ $$=1+\sum_{k=0}^n {n \choose k}a^k$$ $$=1+a^n+\sum_{k=0}^{n-1} {n \choose k}a^k$$ $$\ge\sum_{k=0}^n {a \choose k}+\sum_{k=0}^{n-1} {n \choose k}a^k$$

We now note that $$\sum_{k=0}^{n} {a+1 \choose k}= \sum_{k=0}^{n} \left[{a \choose k}+{a \choose k-1}\right]$$ This mean all we have to prove is that $$\sum_{k=0}^{n-1} {n \choose k}a^k \ge \sum_{k=0}^{n}{a \choose k-1}$$

$\endgroup$
  • $\begingroup$ Sorry I don't understand how proving the last statement can prove the original problem. Can you clarify? $\endgroup$ – ahmad1374 Feb 14 '17 at 12:44

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.