View Single Post
Old 06-11-2015, 12:31 AM
yongxien yongxien is offline
Junior Member
Join Date: Jun 2015
Posts: 8
Default Problem with understanding the proof of Sauer Lemma

I will replicate the proof here which is from the book "Learning from Data"

Sauer Lemma:
$B(N,K) \leq \sum_{i=0}^{k-1}{n\choose i}$

The statement is true whenever k = 1 or N = 1 by inspection. The proof is by induction on N. Assume the statement is true for all $N \leq N_o$ and for all k. We need to prove that the statement for $N = N_0 + 1$ and fpr all k. Since the statement is already true when k = 1(for all values of N) by the initial condition, we only need to worry about $k \geq 2$. By (proven in the book), $B(N_0 + 1, k) \leq B(N_0, k) + B(N_0, k-1)$ and applying induction hypothesis on each therm on the RHS, we get the result.

**My Concern** From what I see this proof only shows that if $B(N, K)$ implies $B(N+1, K)$. I can't see how it shows $B(N, K)$ implies $B(N, K+1)$. This problem arises because the $k$ in $B(N_0 + 1, K)$ and $B(N_0, K)$ are the same, so i think i need to prove the other induction too. Why the author is able to prove it this way?
Reply With Quote