Interpretación combinatoria de una identidad binomial

Question

El puesto original debido a David Peterson es aquí .

Cómo establecer combinatoriamente la siguiente identidad Binomal:

$$\displaystyle \sum\limits_{k = 0}^{[n/2]}\binom{n-k}{k}2^k = \frac{2^{n+1}+(-1)^n}{3} \tag{1}$$

Intento de alicatado $n \times 1$ rectángulo con fichas de dominó ( $2\times 1$ ) de dos colores y cuadrados ( $1 \times 1$ ) de un solo color. Fijación de $k$ para el número de fichas de dominó, podemos contar entre los $n-k$ posiciones en el tablero cuál es una ficha de dominó y una casilla y colorear las fichas de dominó de 2 maneras en $\displaystyle \binom{n-k}{k}2^k$ formas.

En cuanto al lado derecho, tengo problemas. ¿Debo interpretarlo como $\displaystyle \frac{2^{n+1}-(-1)^{n+1}}{2-(-1)} = \sum\limits_{k=0}^{n}2^k(-1)^{n-k}$ y argumentar con algún I.E.P. o es posible argumentar estableciendo una biyección entre tres particiones de $2^{n+1}+(-1)^n$ ¿configuraciones? No consigo averiguar de qué manera.

Nota : Por otro lado podemos argumentar combinatoriamente que L.H.S. de $(1)$ (coloreado de domino) satisface una recursión lineal que se puede demostrar por inducción o de otra manera que es el R.H.S. (pero tampoco estoy buscando eso).

Answer 1

Utilicé otra visión combinatoria para el L.H.S. (denotarlo $f(n)$ ). No he demostrado la fórmula explícitamente por biyección pero puedo mostrar $f(n)=2^n-f(n-1)$ . Puede ser la recursión lineal "no deseada", pero se acerca bastante a la fórmula $\sum_{k=0}^n 2^k(-1)^{n-k}$ aunque no es directamente I.E.P. (bueno I.E.P. tampoco es tan obvio, ¿no?)

$n-k\choose k$ cuenta el número de caminos desde el punto $[0,0]$ al grano $[n-2k, k]$ utilizando pasos (hacia arriba/hacia la derecha) (su longitud es siempre $n-k$ ). $2^k$ cuenta el número de trayectorias de la longitud $k$ (con punto final arbitrario). Componiendo estos caminos se obtiene un camino de la longitud $n$ que pasa por el punto $[n-2k, k]$ .

Un camino no puede pasar por diferentes puntos de la forma $[n-2k,k]$ así que $f(n)$ cuenta tales trayectorias de la longitud $n$ que pasa por alguno. Contemos el complemento: ¿qué caminos no pasan por ninguno de esos puntos? Exactamente los que van a un punto de la forma $[n-2k-1,k]$ y luego hacia arriba hasta el punto $[n-2k-1, k+1]$ . Descartando este paso ascendente obtenemos un camino de la longitud $n-1$ que pasa por un punto de la forma $[(n-1)-2k, k]$ es decir, un objeto contado por $f(n-1)$ .

Editar: Me di cuenta de que en realidad describe una biyección entre trayectorias de la longitud $n, n-2, \ldots$ y caminos de la longitud $n-1, n-3, \ldots$ con caminos contados por $f(n)$ . El algoritmo es: Tomar un camino de longitud $l$ . Si pasa por un punto de la forma $[l-2k, k]$ inserte un paso hacia arriba aquí. En caso contrario, descarta un paso ascendente entre los puntos $[l-2k-1,k]$ y $[l-2k-1, k+1]$ . La única excepción es cuando se debe extender un camino de la longitud $n$ -- entonces déjalo sin cambiar.