VC-Dimension of Real Linear Classifier Proof

Question

Does anyone have know or have a link to a proof of why the VC-Dimension of Linear Classifiers in $\mathbb{R}^n$ is $n+1$? That is the set of $h_a : \mathbb{R}^n \rightarrow \{-1,1\}, h_a(b) = sgn(a \cdot b + k)$ where $a,b \in \mathbb{R}^n, k \in \mathbb{R}$. I tried some Google Fu and I've only seen people state it but not bother to prove it. The proof of $d \ge n+1$ is pretty straightforward but I can't figure out the $d < n+2$ part.

Answer 1

For the $ d < n + 2 $ part I know one proof which relays on the Steele Dudley Theorem.

Unfortunately, the only relevant online reference for this theorem that I managed to find is in Hebrew. But here it is just in case.

The Theorem States:

If $H$ is an hypothesis class where $Dim(H)=n$, then for every series of $n+1$ inputs $\{x_i\}_1^{n+1} $ , we can find a series of $n+1$ binary classifications ($\pm1$) $\{y_i\}_1^{n+1} $ s.t. the series $\{x_i\}_1^{n+1} $ cannot be classified perfectly by any classifier of the form: $sign(h(x))$.

In your case $H$ is all linear classifiers which are determined by $n$ weights and 1 offset. so $Dim(H)=n+1$.

additional reference