0

I'm reading about Cover’s Function Counting Theorem and I want to prove that when $p/N = 2$ it is true that

$$\frac{C(p,N)}{2^p}=\frac12$$

as is shown in the plot in that same link.

In Hertz, Krogh & Palmer's Introduction to the Theory of Neural Computation it is stated that

It is actually easy to show from the symmetry ${{2n}\choose{n-m}}={{2n}\choose{n+m}}$ of binomial coefficients that $$C(2N,N)=2^{p-1}$$

That's exactly the result I want, as is just another way of writing the equality I wrote at the beginning. In sum, what I want to prove is that

$$2\sum\limits_{i=0}^{N-1}{{2N-1}\choose{i}}\stackrel{?}{=}2^{2N-1}$$

I don't know how to start, because the superior limit of the summation doesn't match the upper index of the binomial coefficient. According to the book I quoted, it appears that at some point the symmetry of binomial coefficients should be used, but I can't come up with any ideas.

Tendero
  • 798
  • 1
  • 7
  • 18

1 Answers1

0

So we would like to prove $$2\sum\limits_{i=0}^{N-1}{{2N-1}\choose{i}}\stackrel{}{=}2^{2N-1}$$ First we know: $$1.1.\sum\limits_{i=0}^{2N-1}{{2N-1}\choose{i}}=(1+1)^{2N-1}=2^{2N-1}$$ Secondly we know the rule of symmetry of the binomial coefficients
$${{K}\choose{i}}={{K}\choose{K-i}}\implies{{2N-1}\choose{i}}={{2N-1}\choose{2N-1-i}}$$ The above sum can be written:$$\sum\limits_{i=0}^{2N-1}{{2N-1}\choose{i}}=\sum\limits_{i=0}^{N-1}{{2N-1}\choose{i}}+{{2N-1}\choose{2N-1-i}}=2\sum\limits_{i=0}^{N-1}{{2N-1}\choose{i}}$$ The last equality by the symmetry, and from 1.1 our equality holds. Q.E.D

Alon Yariv
  • 1,363