Thursday 22 January 2015

sequences and series - Prove by induction the upper bound on the sum of binomial co-efficients

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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...