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}$ ??
No comments:
Post a Comment