¿Cómo calcular $\sum\limits_{k=0}^n (-1)^k{2n-k\choose k}$?

Question

Me quedé pegado en el cómputo de la suma de $$ \sum\limits_{k=0}^n (-1) ^ k {2n-k\choose k}. $$ creo que no hay ninguna prueba puramente combinatoria aquí puesto que la suma puede alcanzar valores negativos. Podría usted darme solución, parece implicar la generación de funciones.

Answer 1

De hecho, la generación de la función de método funciona. Deje $c_n$ denoe la suma. Entonces tenemos

$$\begin{align*} \sum_{n=0}^{\infty} c_n y^{2n} &= \sum_{n=0}^{\infty} \sum_{k=0}^{n} \frac{(-1)^k y^{2n}}{(2n-2k)!k!} \int_{0}^{\infty} x^{2n-k} e^{-x} \; dx \\ &= \int_{0}^{\infty} \sum_{k=0}^{n} \sum_{n=0}^{\infty} \frac{(yx)^{2n-2k}}{(2n-2k)!} \frac{(-y^2 x)^k}{k!} e^{-x} \; dx \\ &= \int_{0}^{\infty} \cosh(yx) e^{-(y^2+1)x} \; dx \\ &= \int_{0}^{\infty} \frac{1}{2} \left( e^{-(y^2-y+1)x} + e^{-(y^2+y+1)x} \right) \; dx \\ &= \frac{1}{2} \left( \frac{1}{y^2 - y + 1} + \frac{1}{y^2 + y + 1} \right) \\ &= \frac{1 - y^4}{1 - y^6} \\ &= 1 - y^4 + y^6 - y^{10} + \cdots. \end{align*}$$

Así, mediante la comparación de los coeficientes, tenemos

$$ c_n = \begin{cases} 1 & n \equiv 0 \ (\mathrm{mod} \ 3) \\ 0 & n \equiv 1 \ (\mathrm{mod} \ 3) \\ -1 & n \equiv 2 \ (\mathrm{mod} \ 3) \end{casos}.$$

Similares cálculo también muestra que

$$ \sum_{k=0}^{n} \binom{2n-k}{k} = F_{2n+1},$$

donde $F_0 = 0, F_1 = 1$ $F_{n+2} = F_{n+1} + F_n$ es la secuencia de Fibonacci.

---

Bueno, aquí es un enfoque directo, motivado por el Cerebro M. Scott iluminando respuesta. Por el triángulo de Pascal

$$\begin{align*} c_{n+1} &= \sum_{k=0}^{n+1}(-1)^k \binom{2n+2-k}{k} \\ &= \sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k-1} + \sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k} \\ &= - \sum_{k=0}^{n+1}(-1)^k \binom{2n-k}{k} + \sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k} \\ &= - c_n + \sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k}. \end{align*}$$

Pero aplicando exactamente la misma técnica que la última suma, tenemos

$$\begin{align*} \sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k} &= \sum_{k=0}^{n+1}(-1)^k \binom{2n-k}{k-1} + \sum_{k=0}^{n+1}(-1)^k \binom{2n-k}{k} \\ &= - \sum_{k=0}^{n}(-1)^k \binom{2n-1-k}{k} + \sum_{k=0}^{n}(-1)^k \binom{2n-k}{k} \\ &= - \sum_{k=0}^{n}(-1)^k \binom{2n-1-k}{k} + c_n. \end{align*}$$

Volver a conectar, obtenemos

$$ c_{n+1} = - \sum_{k=0}^{n}(-1)^k \binom{2n-1-k}{k}.$$

Así tenemos

$$c_{n+1} = - c_n + \sum_{k=0}^{n+1}(-1)^k \binom{2n+1-k}{k} = - c_n - c_{n+2},$$

o, equivalentemente,

$$c_{n+2} + c_{n+1} + c_n = 0.$$

Así que tenemos $c_{n+3} = c_n$ y la prueba está completa.

Answer 2

Esto no va a ser una buena respuesta. Más bien, se ilustrará cómo se puede atacar el problema desde cero, sin utilizar nada especialmente sofisticado.

Deje $$a_n=\sum_{k=0}^n(-1)^n\binom{2n-k}k\;.$$

Desde el triángulo de Pascal tenemos

$$\begin{align*} \binom{2(n+1)-k}k&=\binom{2n+1-k}{k-1}+\binom{2n+1-k}k\\ &=\binom{2n-k}{k-2}+2\binom{2n-k}{k-1}+\binom{2n-k}k\;, \end{align*}$$

por lo que $$\begin{align*} \sum_{k=0}^{n+1}(-1)^k\binom{2(n+1)-k}k&=\sum_{k=0}^{n+1}(-1)^k\left(\binom{2n-k}{k-2}+2\binom{2n-k}{k-1}+\binom{2n-k}k\right)\\ &=\sum_{k=0}^{n+1}(-1)^k\binom{2n-k}{k-2}+2\sum_{k=0}^{n+1}(-1)^k\binom{2n-k}{k-1}+\\ &\qquad\qquad+\sum_{k=0}^{n+1}(-1)^k\binom{2n-k}k\\ &=\sum_{k=0}^{n-1}(-1)^k\binom{2(n-1)-k}k-2\sum_{k=0}^{n-1}(-1)^k\binom{2n-1-k}k+\\ &\qquad\qquad+\sum_{k=0}^n(-1)^k\binom{2n-k}k\;, \end{align*}$$

o $$a_{n+1}=a_{n-1}+a_n-2\sum_{k=0}^{n-1}(-1)^k\binom{2n-1-k}k\;.\tag{0}$$

Si pudiéramos conseguir una manija en la suma en la parte derecha, nos gustaría estar en el negocio. Ahora

$$\begin{align*} \sum_{k=0}^{n-1}(-1)^k\binom{2n-1-k}k&=\sum_{k=0}^{n-1}(-1)^k\left(\binom{2(n-1)-k}k+\binom{2(n-1)-k}{k-1}\right)\\ &=\sum_{k=0}^{n-1}(-1)^k\binom{2(n-1)-k}k-\sum_{k=0}^{n-2}(-1)^k\binom{2(n-1)-1-k}k\\ &=a_{n-1}-\sum_{k=0}^{n-2}(-1)^k\binom{2(n-1)-1-k}k\;,\tag{1} \end{align*}$$

donde la suma de la derecha es igual que la que hay en el lado izquierdo, pero con $n$ reemplazado por $n-1$. Que sugiere que debemos dejar $$b_n=\sum_{k=0}^{n-1}(-1)^k\binom{2n-1-k}k$$ and write $(1)$ as $$b_n=a_{n-1}-b_{n-1}\;.$$ Since $b_0=0$, this boils down to $$b_n=\sum_{k=0}^{n-1}(-1)^{n-1-k}a_k\;,$$ while $(0)$ can be rewritten as $$a_{n+1}=a_n+a_{n-1}-2b_n=a_n-a_{n-1}+2\sum_{k=0}^{n-2}(-1)^{n-k}a_k\;.$$

En particular, $$a_{n+3}=a_{n+2}-a_{n+1}+2\sum_{k=0}^n(-1)^{n-k}a_k\;,\tag{2}$$ and you know that $a_0=1,a_1=0,a_2=-1$, and the sequence seems to repeat with a period of $3$. Can you now use $(2)$ demostrar por inducción que este es realmente el caso?

En concreto, usted querrá demostrar por inducción simultánea que

$$a_n=\begin{cases} 1,&\text{if }n\equiv 0\pmod 3\\ 0,&\text{if }n\equiv 1\pmod 3\\ -1,&\text{if }n\equiv 2\pmod 3\;, \end{casos}$$ and $$b_n=\begin{cases} 1,&\text{if }n\equiv 0\pmod 3\\ -1,&\text{if }n\equiv 1\pmod 3\\ 0,&\text{if }n\equiv 2\pmod 3\;. \end{casos}$$

Answer 3

Hay una combinatoria de la prueba.

En primer lugar, $\binom{2n-k}{k}$ es el número de maneras de baldosa una línea de consejo de $2n$ células con $k$ dominó y $2n-2k$ plazas. (Fichas de dominó tomar hasta dos células, y las plazas de tomar uno de ellos.) Esto es porque usted tiene $2n-k$ total de las baldosas en un suelo de baldosas, y hay $\binom{2n-k}{k}$ maneras de elegir cuáles son las fichas de dominó.

Así $$\sum_{k=0}^n \binom{2n-k}{k} (-1)^k$$ is the difference in the number of tilings of a $2n$-junta de que el uso de un incluso el número de fichas de dominó y el número de apuntados que el uso de una extraña serie de fichas de dominó.

Vamos a decir que un suelo de baldosas es irrompible en la celda $k$ si un domino ocupa células de $k$$k+1$.

A partir de aquí, vamos a proceder en los casos. Supongamos $2n\equiv 2\pmod 3$. Dado un mosaico de la $2n$-junta, encontrar el primer frágiles células de la forma $3j+2$. Debe ser una celda porque la última celda es de esta forma. Por no estar no se pueden romper las células de la forma $3i+2$ $i < j$ el revestimiento debe ser de forma cuadrada, domino, cuadrado, domino, etc., arriba a través de la celda $3j$. Si las células de la $3j+1$ $3j+2$ están cubiertos por una ficha de dominó, dividirlo en dos plazas. Si las células de la $3j+1$ $3j+2$ está cubierto por dos plazas, reemplazarlos con una ficha de dominó. Esta asignación es reversible, y cambia la paridad en el número de fichas de dominó. Por lo tanto, cuando se $2n\equiv 2\pmod 3$ hay muchos apuntados de la $2n$-de la junta, ya que hay impar apuntados, como cada mosaico en este caso debe tener al menos un frágiles células de la forma $3j+2$.

Si $2n \not\equiv 2 \pmod 3$, entonces no es exactamente un mosaico que es irrompible en todas las células de la forma $3j+2$. Si $2n \equiv 0 \pmod 3$, entonces este es el mosaico que consiste en la plaza, domino, cuadrado, domino, etc., para toda la longitud de la junta, que termina en una ficha de dominó. Así pues, en este mosaico hay $d$ dominó y $s$ plazas que $2n = 2d+s = 3d$, ya que el $d=s$ en este caso. Pero si $3d = 2n$,$2|d$, y así los restos de mosaico tiene paridad par.

Si $2n \equiv 1 \pmod 3$, luego los restos de mosaico se compone de la plaza, domino, cuadrado, domino, etc., para toda la longitud de la junta, que termina en una plaza. Así pues, en este mosaico $d+1 = s$, y así obtenemos $2n = 2d+s = 3d+1$. Esto significa significa que $d$ no puede ser divisible por $2$, y así los restos de mosaico tiene paridad impar.

Poner todos los tres casos tenemos $$ \sum_{k=0}^n \binom{2n-k}{k} (-1)^k =\begin{cases} 1,&\text{if }2n\equiv 0\pmod 3;\\ -1,&\text{if }2n\equiv 1\pmod 3;\\ 0,&\text{if }2n\equiv 2\pmod 3. \end{casos}$$

(Referencia: Identidad 172, páginas 85-86, en Benjamín y Quinn Pruebas de que Realmente Cuentan.)

Answer 4

Vamos $$ a_n=\sum_{k=0}^n(-1)^k\binom{n-k}{k} $$ Tomando nota de que $$ \sum_{n=k}^\infty\binom{n}{k}x^n=\frac{x^k}{(1-x)^{k+1}}\etiqueta{1} $$ podemos calcular la generación de la función de $a_n$: $$ \newcommand{\cis}{\operatorname{cis}} \begin{align} \sum_{n=0}^\infty a_nx^n &=\sum_{n=0}^\infty x^n\sum_{k=0}^n(-1)^k\binom{n-k}{k}\\ &=\sum_{k=0}^\infty\sum_{n=k}^\infty(-1)^kx^n\binom{n-k}{k}\\ &=\sum_{k=0}^\infty\sum_{n=0}^\infty(-1)^kx^{n+k}\binom{n}{k}\\ &=\sum_{k=0}^\infty(-1)^kx^k\frac{x^k}{(1-x)^{k+1}}\\ &=\frac{1}{1-x}\sum_{k=0}^\infty(-1)^k\left(\frac{x^2}{1-x}\right)^k\\ &=\frac{1}{1-x}\frac{1}{1+\frac{x^2}{1-x}}\\ &=\frac{1}{1-x+x^2}\\ &=\frac{1}{\alpha-\beta}\left(\frac{1}{x-\alpha}-\frac{1}{x-\beta}\right)\tag{2} \end{align} $$ donde $\alpha$ $\beta$ son las raíces de $1-x+x^2=0$; $\alpha=\cis(\pi/3)$ y $\beta=\cis(-\pi/3)$.

Por lo tanto, las series de $(2)$ es $$ \begin{align} &\frac{1}{\cis(\pi/3)-\cis(-\pi/3)}\left(\frac{\cis(\pi/3)}{1-\cis(\pi/3)x}-\frac{\cis(-\pi/3)}{1-\cis(-\pi/3)x}\right)\\ &=\frac{2}{\sqrt{3}}\Im\left(\frac{\cis(\pi/3)}{1-\cis(\pi/3)x}\right)\\ &=\frac{2}{\sqrt{3}}\Im\left(\sum_{n=0}^\infty\cis((n+1)\pi/3)x^n\right)\tag{3} \end{align} $$ Por lo tanto, $$ a_n=\frac{2}{\sqrt{3}}\sin\left(\frac{n+1}{3}\pi\right)\etiqueta{4} $$ y la secuencia requerida es $$ a_{2n}=\frac{2}{\sqrt{3}}\sin\left(\frac{2n+1}{3}\pi\right)\etiqueta{4} $$

Answer 5

Considerar el más general número $C_n$ definidas como

$$ C_n = \sum_{k = 0} ^ {\infty} (-1) ^ k {k n \choose k} $$

donde ${m \choose k} = 0$ si $k > m$. Luego, sus números son $C_{2n}$ $n = 0, 1, 2, \dots$. Estos números satisfacen

$$\begin{eqnarray} C_n &=& \sum_{k = 0}^{\infty}(-1)^k\left( {n-1-k \choose k} + {n-1-k \choose k-1} \right)\\ &=& C_{n-1} - \sum_{k = 0}^{\infty} (-1)^k {n - 2 - k \choose k}\\ &=& C_{n-1} - C_{n-2} \end{eqnarray} $$

La secuencia $C_0, C_1, C_2, \dotsc$ es, por tanto

$$ 1, 1, 0, -1, -1, 0, 1, 1, 0, -1, \dotsc $$

y sacar el % de términos incluso $C_0, C_2, C_4, \dotsc$da la secuencia

$$ 1, 0, -1, 1, 0, -1, \dotsc $$

En otras palabras $C_{2n} = (2 - n \mod 3) - 1$.