Learning From Data – A Short Course: Problem 2.5

Page 69, Problem 2.5.

Prove by induction that \sum_{i=0}^{D}\binom{N}{i} \leq N^{D} + 1, hence

    \[ m_{H} (N) \leq N^{d_{vc}} + 1 \]

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} \]

We will prove  \frac {N!}{(N-D)!} \leq N^{D} later, for now, we 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.


Prove by induction:

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

Base case:

D = 0: \frac {N!}{(N-0)!} \leq N^{0} \Leftrightarrow 1 \leq 1

Induction step for D > 0 :

    \[ \frac {N!}{(N-D)!} = \frac {N!}{(N-(D-1))!}(N-(D-1)) \leq N^{D-1}(N - (D - 1)) \]

    \[ N^{D-1}(N - (D - 1)) = N^{D} - (D - 1)N^{D-1} \]

(D - 1) \geq 0, N^{D-1} \geq 1 \Rightarrow (D - 1)N^{D-1} \geq 0 \Leftrightarrow - (D - 1)N^{D-1} \leq 0 :

    \[ N^{D} - (D - 1)N^{D-1} \leq N^{D} \]

So  \frac {N!}{(N-D)!} \leq N^{D} follows.

Shorter solution (by a friend of mine):

    \[ \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 \]


Facebooktwittergoogle_plusredditpinterestlinkedinmail

1 comment on “Learning From Data – A Short Course: Problem 2.5”

Leave a Reply

Your email address will not be published. Required fields are marked *