Problem 2.5

CountVonCount · #1 10-25-2016, 02:46 AM

Hello,

I tried to prove the unequally of problem 2.5 on page 69:

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

However I was not able to find a good prove. I tried by using the same scheme like in the prove for

$\sum_{i=0}^{N}{\binom{N}{i}} = 2^N$

But I had no success.

Can anyone give me the answer or at least a hint, how to start the prove well?

Thanks a lot,
André

P.S.: Is there a good way to embedd latex to this Forum? At the moment I just use https://www.codecogs.com for generating latex pictures.

P.P.S.: The book is very good and the course videos make a lot of fun to watch. Really: Thanks to everyone who worked on it!

ntvy95 · #2 11-14-2016, 09:18 PM

I hope that I didn't make any mistake.

Base cases:

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

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

: $\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$

Induction step for

:

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

I will prove $\frac {N!}{(N-D)!} \leq N^{D}$ later, for now, I will use its result:

$N^{D-1} + 1 +\binom{N}{D} \leq N^{D-1} + 1 + \frac {N^{D}}{D!}$

$D > 2 \Rightarrow D! > 2 \Leftrightarrow \frac{1}{D!} < \frac{1}{2}$ :

$N^{D-1} + 1 + \frac {N^{D}}{D!} \leq N^{D-1} + 1 + \frac {N^{D}}{2}$

$D > 2, N \geq D \Rightarrow N > 2 \Leftrightarrow \frac {1}{N} < \frac {1}{2} \Leftrightarrow \frac {N^{D-1}}{N^{D}} < \frac {1}{2} \Leftrightarrow N^{D-1} < \frac {N^{D}}{2}$ :

$N^{D-1} + 1 + \frac {N^{D}}{2} \leq \frac {N^{D}}{2} + 1 + \frac {N^{D}}{2} \leq N^{D} + 1$

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

Quote:

Prove:

$\frac {N!}{(N-D)!} \leq N^{D}$

$\frac{1}{N^{D}} \times \frac {N!}{(N-D)!} = \frac{1}{N^{D}} \times \prod_{i=0}^{D+1} (N - i) = \prod_{i=0}^{D+1} \frac{N - i}{N^{D}} \leq 1$

k_sze · #3 03-16-2018, 10:07 AM

Quote:

Originally Posted by ntvy95

$\frac{1}{N^{D}} \times \frac {N!}{(N-D)!} = \frac{1}{N^{D}} \times \prod_{i=0}^{D+1} (N - i) = \prod_{i=0}^{D+1} \frac{N - i}{N^{D}} \leq 1$

Aside from the slight mistake in the product (it should be $\prod_{i=0}^{D-1} (N - i)$ ), the whole proof is just amazing! How did you even come up this chain of logic and deduction?

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode