El cálculo de $\sum_{0\le k\le n/2} \binom{n-k}{k}$

Question

Me gustaría evaluar:

$$\sum_{0\le k\le n/2}\binom{n-k}{k}$$

Alguna idea?

Answer 1

SUGERENCIA

Si usted trata de un par de valores de $n$ usted debe ver el patrón $$\sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n-k}{k}= F_{n+1}$$ where $F_n$ is the $$n-ésimo número de Fibonacci. Con esto en mente, usted puede emplear el método de inducción.

Así que asumir que existe $n\in\mathbb{N}$ s.t $$\sum_{k=0}^{\lfloor (n-1)/2 \rfloor}\binom{n-1-k}{k}= F_n , \mbox{ and } \sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n-k}{k}=F_{n+1}$$

Desea, a continuación, mostrar $$ \sum_{k=0}^{\lfloor (n-1)/2 \rfloor}\binom{n-1-k}{k} + \sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n-k}{k} = \sum_{k=0}^{\lfloor (n+1)/2 \rfloor}\binom{n+1-k}{k}$$

Esto puede parecer complicado, pero es sencillo si se observa un diagrama del triángulo de Pascal para que los guíe.

---

Otro método si a través de Zeckendorf del Teorema que dice que todo entero positivo se puede expresar de manera única como la suma de la no-consecutivos de números de Fibonacci. Observe que la suma tenemos cuenta de que el número de subconjuntos de a $ \{ F_2, F_3, \cdots F_n \} $ sin consecutivos miembros, y la suma de los elementos de cada uno de los subconjuntos da enteros $0, 1,2,3\cdots, F_{n+1}-1 $.

Answer 2

Ragib la respuesta puede ser formulado de una manera más combinatoria manera:

Es bien sabido, que el $F_{n+1}$ es el número de formas que puede revestir un $1\times n$ junta con $1\times 2$ dominó y $1\times 1$ plazas.

$\binom{n-k}{k}$ contadores de mosaicos que contengan $k$ fichas de dominó (y $n-2k$ plazas), por lo que la fórmula de la siguiente manera.

Answer 3

Considere la posibilidad de la generación de la función $$f(z) = \sum_{n\ge 0} z^n \sum_{k=0}^{\lfloor n/2 \rfloor} {n-k\choose k}$$ y re-escribirlo en términos de $k$ como sigue $$f(z) = \sum_{k\ge 0} \sum_{\lfloor n/2 \rfloor \ge k} z^n {n-k\elegir k} = \sum_{k\ge 0} \sum_{n\ge 2k} {n-k\elegir k} z^n = \sum_{k\ge 0} \sum_{n\ge 0} {n+k\elegir n} z^{n+2k}.$$ Ahora el binomio de Newton puede ser aplicado al interior de la suma para obtener $$f(z) = \sum_{k\ge 0} z^{2k} \frac{1}{(1-z)^{k+1}} = \frac{1}{1-z}\frac{1}{1-z^2/(1-z)} = \frac{1}{1-z-z^2}.$$ Esta es visto como la OGF de $F_{n+1}$ ($n+1$-ésimo número de Fibonacci) y hemos terminado.

El mismo truco se utiliza aquí en este MSE enlace.