1
$\begingroup$

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

$B(N, k)$ is the maximum number of dichotomies on $N$ points such that no subset of size $k$ of the $N$ points can be shattered by these dichotomies.

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

Proof: 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$. 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?

$\endgroup$
2
  • $\begingroup$ @BruceTrumbo edited $\endgroup$ Commented Jun 11, 2015 at 7:12
  • $\begingroup$ I think that you don't need other induction unless you want to understand why $B(N_0 + 1, k) \leqslant B(N_0, k) + B(N_0, k-1)$ (and I'm not sure that its proof necessarily needs induction). $\endgroup$
    – Evgeny
    Commented Jul 22, 2015 at 6:20

1 Answer 1

0
$\begingroup$

The key is that the statement is assumed to be true for all $N\leq N_0$ and for all $k$.

So your induction hypothesis is $H(N)$: for all $k$, $$B(N,k)\leq \sum_{i-0}^{k-1} {N\choose i}$$

The base case $H(1)$ is true (it can be shown "by inspection").

You now assume that $H(N)$ is true for all $N\leq N_0$ and show that $H(N_0+1)$ is true.

Thus you have to prove that for all $k$, $$B(N_0,k)\leq \sum_{i-0}^{k-1} {N_0\choose i}$$ First, for $k=1$ you know it is true ("by inspection"). Then for $k\geq 2$ you use that $B(N_0+1,k)\leq B(N_0,k)+B(N_0,k−1)$ and since your induction hypothesis claims that all $k$, $B(N,k)\leq \sum_{i-0}^{k-1} {N\choose i}$ you can apply it on $B(N_0,k)$ and $B(N_0,k−1)$, and obtain that for all $k\geq 2$ $B(N_0+1,k)\leq \sum_{i-0}^{k-1} {N_0+1\choose i}$

This prove that $k$, $B(N_0+1,k)\leq \sum_{i-0}^{k-1} {N_0+1\choose i}$ hence $H(N_0+1)$.

Which conclude the induction.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .