¿Cómo calcular la suma de cada$k$ - coeficiente binomial?

Question

Mi maestro estaba hablando del binomio expansiones de $(1 + x)^n$ y dio un ejemplo interesante con $x = i$ el cual se puede obtener la suma de todos los coeficientes impares ($C_n^1+ C_n^3+ C_n^5 ...$) y el aún. Entonces por appying deMoivre a $(1 + i)^n$ usted podría separar el binomio de expansión en una real y una parte imaginaria y calcular de ellos por separado.

¿Cómo puedo yo, un tanto similar manera, determinar la suma de cada k-ésimo coeficiente binomial, el uso de la kth la unidad de la raíz?

Sustituyendo en $(1 + x)^n$ todos los de la unidad raíces en uno y, a continuación, agregar los resultados de los resultados es la suma de cada k-ésimo coeficiente es igual a$(1 + 1)^n + (1 + \omega)^n + (1 + \omega^2)^n$, pero ¿cómo puedo obtener la forma cerrada para esta suma?

Answer 1

La palabra clave es la transformada de Fourier discreta. El basic lema es que si $\zeta_k$ es una primitiva $k^{th}$ raíz de la unidad, a continuación,

$$\sum_{i=0}^{k-1} \zeta_k^{ij} = \begin{cases} 0 \text{ if } k \nmid j \\ k \text{ otherwise}. \end{cases}$$

De ello se sigue que si $f(x) = \sum a_i x^i$ es un poder formal de la serie, a continuación, la suma de todos los $k^{th}$ plazo de $f$ es

$$\sum a_{ki} x^{ki} = \frac{1}{k} \sum_{i=0}^{k-1} f(\zeta_k^i x).$$

En este caso particular tenemos, por ejemplo,

$$\sum {n \choose 2i} = \frac{1}{2} \left( (1 + 1)^n + (1 - 1)^n \right) = 2^{n-1}$$

y

$$\sum {n \choose 3i} = \frac{1}{3} \left( (1 + 1)^n + (1 + \omega)^n + (1 + \omega^2)^n \right) = \frac{2^n + (-\omega^2)^n + (-\omega)^n}{3}$$

donde $\omega$ es una primitiva de la tercera raíz de la unidad (y hemos utilizado el hecho de que $1 + \omega + \omega^2 = 0$). La respuesta es messier en general.