A finite sum over $\pm 1$ vectors

Question

$$\mbox{What is a nice way to show}\quad \sum_{\vphantom{\Large A}u\ \in\ \left\{-1,+1\right\}^{N}} \left\vert\,\sum_{i\ =\ 1}^{N}u_{i}\,\right\vert = N{N \choose N/2} \quad\mbox{when}\ N\ \mbox{is even ?.} $$ Could there be a short inductive proof ?.

Answer 1

If there are $r$ -1s in $u$, then $|\sum u_i| = |N-2r|$

Let $M = \frac{N}{2} -1$. Thus we are looking at

$$ \sum_{r=0}^{N} \binom{N}{r} |N - 2r| = 2\sum_{r=0}^{M} \binom{N}{r} (N-2r) $$

(using $\binom{N}{r} = \binom{N}{N-r}$)

Now if $P(x) = \sum_{k=0}^{N} a_k x^k$, then the partial sum $a_o + a_1 + \dots + a_i$ is given by the coefficient of $x^i$ in the series expansion of $\dfrac{P(x)}{1-x}$

Let $$Q(x) = \sum_{r=0}^{N} q_r x^r = \sum_{r=0}^{N} \binom{N}{r}(N-2r)x^r = N\sum_{r=0}^{N} \binom{N}{r}x^r - \sum_{r=0}^{N} \binom{N}{r}2rx^r =$$ $$= N(1+x)^N - 2xN(1+x)^{N-1} = N(1+x)^{N-1}(1-x)$$

(We used: $(1+x)^N = \sum_{r=0}^{N} \binom{N}{r} x^r$ and then differentiate and multiply by $x$)

We are interested in the partial sums of the coefficients of $Q(x)$: $2(q_0 + q_1 + \dots + q_M)$

Thus we need to look at the coefficient of $x^M$ in $\dfrac{Q(x)}{1-x} = N(1+x)^{N-1}$, which is $N\binom{N-1}{M}$.

Thus your answer is $$ 2N \binom{N-1}{M}$$ which easily simplifies to $$ N \binom{N}{N/2}$$

(remember, $M = \frac{N}{2} -1$)

Answer 2

Since $\sum_{i=1}^N|u_i|=||u||_1$ and $u\in \{-1,1\}^N$, we see that there are $\binom{N}{k}$ vectors $u$ which has $k$ $1$'s, $0\le k\le N$. Thus the required sum can be rewritten as $$\sum_{k=0}^N|2k-N|\binom{N}{k}=\sum_{k=0}^{N/2}(N-2k)\binom{N}{k}+\sum_{k= N/2+1}^N(2k-N)\binom{N}{k}\\ =N\binom{N}{N/2}+\sum_{k=N/2+1}^{N}2k \binom{N}{k}-\sum_{k=0}^{N/2} 2k\binom{N}{k}\\=N\binom{N}{N/2}+2N\sum_{k=N/2}^{N-1}\binom{N-1}{k}-2N\sum_{k=0}^{N/2-1}\binom{N-1}{k}$$ It can be easily seen that the last two terms sum to $0$. So the result follows.

Answer 3

Here is a recurrence relation (I doubt it will be of much use, but maybe it can help you in some way.

$s_{n+2}=2s_n+\sum_{i=0}^{N-2}\binom{N-2}{i}(|2i-N+2+2|+|2i-N+2-2|)$

It works by noting that for every sequence in $\{1,-1\}^{N-2}$ there are two ways of extending it without affecting the sum (by adding $-1,1$ or by adding $1,-1$), this gives the $2s_n$ term. There is one way to extend it by appending $2$ $1$s, this give the $\sum_{i=0}^{N-2}\binom{N-2}{i}|2i-N+2+2|$ term. And there is one way to extend it by appending $2$ $-1$s, this gives the $\sum_{i=0}^{N-2}\binom{N-2}{i}|2i-N+2-2|$ term.

Again, i doubt it can be of much use. And even if you can somehow use a prove by induction from here I'm pretty sure it will be longer than the answer provided by Aryabhata.