Una suma finita $\pm 1$ vectores

Question

$$\mbox {¿Qué es una buena manera de mostrar}\quad \sum_{\vphantom{\Large A}u\ \en\ \left\{-1,+1\right\}^{N}} \left\vert\,\sum_{i\ =\ 1}^{N}u_{i}\,\right\vert = N{N \elegir N/2} \quad\mbox{si}\ N\ \mbox{es aún ?.} $$ Podría haber un corto inductivo de la prueba ?.

Answer 1

Si hay $r$ -1s en $u$, $|\sum u_i| = |N-2r|$

Deje $M = \frac{N}{2} -1$. Así que estamos mirando

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

(el uso de $\binom{N}{r} = \binom{N}{N-r}$)

Ahora si $P(x) = \sum_{k=0}^{N} a_k x^k$, entonces la suma parcial $a_o + a_1 + \dots + a_i$ está dado por el coeficiente de $x^i$ en la expansión de la serie de $\dfrac{P(x)}{1-x}$

Deje $$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)$$

(Hemos utilizado: $(1+x)^N = \sum_{r=0}^{N} \binom{N}{r} x^r$ y, a continuación, se diferencian y se multiplica por $x$)

Estamos interesados en las sumas parciales de los coeficientes de $Q(x)$: $2(q_0 + q_1 + \dots + q_M)$

Por lo tanto, tenemos que mirar a el coeficiente de $x^M$$\dfrac{Q(x)}{1-x} = N(1+x)^{N-1}$,$N\binom{N-1}{M}$.

Por lo tanto su respuesta es $$ 2N \binom{N-1}{M}$$, que fácilmente se simplifica a $$ N \binom{N}{N/2}$$

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

Answer 2

Desde $\sum_{i=1}^N|u_i|=||u||_1$$u\in \{-1,1\}^N$, vemos que hay $\binom{N}{k}$ vectores $u$ a que $k$ $1$'s, $0\le k\le N$. Por lo tanto la suma requerida puede escribirse como $$\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$. Así, el resultado de la siguiente manera.

Answer 3

Aquí es una relación de recurrencia (dudo que va a ser de mucho uso, pero tal vez se pueda ayudar de alguna manera.

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

Funciona al tomar en cuenta que para cada secuencia en $\{1,-1\}^{N-2}$ hay dos maneras de extender sin afectar la suma (mediante la adición de $-1,1$ o por la adición de $1,-1$), esto le da el $2s_n$ plazo. Hay una manera de extender anexando $2$ $1$s, esto para dar a la $\sum_{i=0}^{N-2}\binom{N-2}{i}|2i-N+2+2|$ plazo. Y hay una manera de extender anexando $2$ $-1$s, esto le da a la $\sum_{i=0}^{N-2}\binom{N-2}{i}|2i-N+2-2|$ plazo.

De nuevo, creo que no puede ser de mucho uso. E incluso si de alguna manera se puede utilizar una prueba por inducción a partir de aquí, estoy bastante seguro de que va a ser más largo que la respuesta proporcionada por Aryabhata.