Thread: Problem 2.5
View Single Post
  #2  
Old 11-14-2016, 09:18 PM
ntvy95 ntvy95 is offline
Member
 
Join Date: Jan 2016
Posts: 37
Default Re: Problem 2.5

I hope that I didn't make any mistake.

Base cases:

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

Induction step for D > 2:

\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
Reply With Quote