¿Cómo demuestro esta identidad combinatoria?

Question

Mostrar que

$${2n \choose n} + 3{2n-1 \choose n} + 3^2{2n-2 \choose n} + \cdots + 3^n{n \choose n} \\ = {2n+1 \choose n+1} + 2{2n+1 \choose n+2} + 2^2{2n+1 \choose n+3} + \cdots + 2^n{2n+1 \choose 2n+1}$$

Una manera en que yo lo hice fue usar la idea de la generación de funciones. Por el lado izquierdo de la expresión, me pueden encontrar 2 funciones. Considerar;

$$f_1 (x) = \frac{1}{(1-3x)} \\ = 1 + 3^1x + 3^2x^2 + 3^3x^3 + \cdots + 3^nx^n + \cdots \\ f_2(x) = \frac{1}{(1-x)^{n+1}} \\ = {n \choose n} + {n+1 \choose n}x + {n+2 \choose n}x^2 + \cdots + {2n-1 \choose n}x^{n-1} + {2n \choose n}x^n + \cdots + $$

Considerar el coeficiente de $x^n$ en la expansión de $f_1 (x) . f_2 (x)$. A continuación, el coeficiente será la expresión en el lado izquierdo.

Ahora además consideramos 2 funciones por el lado derecho de la expresión.

Considerar;

$$f_3 (x) = \frac {1}{(1-2x)} \\ = 1 + 2^1 + 2^2x^2 + \cdots + 2^{n-1}x^{n-1} + 2^nx^n + \cdots \\ f_4 (x) = (1+x)^{2n+1} \\= 1 + {2n+1 \elegir 1}x + \cdots + {2n+1 \elegir n-1}x^{n-1} + {2n+1 \elegir n}x^n +\cdots + {2n+1 \elegir 0}x^{2n +1} \\ = {2n+1 \elegir 2n+1} + {2n+1 \elegir 2n}x + {2n+1 \elegir 2n-1}x^2 + \cdots + {2n+1 \elegir n+2}x^{n-1} + {2n+1 \elegir n+1}x^{n} + \\ + {2n+1 \elegir n}x^{n+1} +\cdots + {2n+1 \elegir 0}x^{2n +1}$$

Por lo tanto el coeficiente de $x^n$ es el coeficiente de $x^n$ en la expansión de $f_3(x) . f_4(x)$

Esto es lo que he conseguido hasta ahora. No estoy seguro de si $f_1(x) .f_2(x) = f_3(x).f_4(x)$. Si las dos funciones son de hecho iguales, entonces puedo concluir que su coeficiente de $x^n$ debe ser igual, que inmediatamente responder a la pregunta. Si son iguales, ¿cómo puedo demostrar que son?

Si las dos funciones no son iguales? ¿Cómo debo proceder para mostrar esta pregunta?

Edit: no podría ser cierto que el producto de las dos funciones son iguales. Traté de sustituir $x=0.1, n=1$. Parece que los dos valores no son iguales. ¿Cómo proceder con esta pregunta?

Answer 1

Aquí está una combinatoria de la prueba. Ambos lados de la ecuación responder a la siguiente pregunta:

¿Cuántas secuencias de longitud $2n+1$, con entradas en $\{0,1,2\}$, de tal manera que

• al menos una de las entradas es un $2$, y
• hay exactamente $n$ ceros a la izquierda de la izquierda, $2$?

LHS:

Supongamos que la izquierda $2$ se produce en el spot $k+1$. Entre las $k$ spots antes de la mano, usted debe elegir a $n$ de las entradas a cero. El $2n+1-(k+1)=2n-k$ spots después de esto puede ser cualquier cosa. Hay $\binom{k}n3^{2n-k}$ maneras de hacer esto. A continuación, suma más de $k$.

RHS:

Supongamos que hay $j$ entradas que son iguales a $0$ o $2$. Seleccione esas entradas que son iguales a $0$ o $2$ en $\binom{2n+1}j$ maneras. A la izquierda de $n$ de estas entradas debe ser igual a cero, el $(n+1)^{st}$ entrada debe ser de dos, luego el resto de la $j-(n+1)$ entradas puede ser elegido libremente entre las $0$ e $2$. Hay $\binom{2n+1}{j}2^{j-(n+1)}$ maneras de hacer esto, entonces la suma de $j$.

Answer 2

Buscamos mostrar que

$$\sum_{q=0}^n {2n-p\elegir n} 3^q = \sum_{q=0}^n {2n+1\elegir n+1+q} 2^q.$$

Tenemos para la LHS

$$\sum_{q=0}^n {2n-p\elegir n-q} 3^q = \sum_{q=0}^n 3^p [z^{n-q}] (1+z)^{2n-p} \\ = [z^n] (1+z)^{2n} \sum_{q=0}^n 3^q z^q (1+z)^{-q}.$$

El coeficiente de extractor de controles de la gama y obtenemos

$$[z^n] (1+z)^{2n} \sum_{q\ge 0} 3^q z^q (1+z)^{-q} = [z^n] (1+z)^{2n} \frac{1}{1-3z/(1+z)} \\ = [z^n] (1+z)^{2n+1} \frac{1}{1-2z}.$$

Podríamos concluir en este punto por la inspección. Continuar de todos modos nos para obtener la RHS

$$\sum_{q=0}^n {2n+1\elegir n-q} 2^q = \sum_{q=0}^n 2^p [z^{n-q}] (1+z)^{2n+1} \\ = [z^n] (1+z)^{2n+1} \sum_{q=0}^n 2^p z^q.$$

El coeficiente de extractor, una vez más, los controles de la gama y obtenemos

$$[z^n] (1+z)^{2n+1} \sum_{q\ge 0} 2^p z^q = [z^n] (1+z)^{2n+1} \frac{1}{1-2z}.$$

Las dos funciones de generación son los mismos y tenemos la igualdad de la LHS y RHS.

Answer 3

El uso de sus funciones, considere la posibilidad de $$ 3^n f_2(\frac13) = 3^n \frac{1}{(1-\frac13)^{n+1}} = \frac32 (\frac92)^n\\ = {n \elegir n}3^n + {n+1 \elegir n}3^{n-1} + \cdots + {2n \elegir n} + {\color{red}{ {2n +1 \elegir n} 3^{-1}+ \cdots}} $$ y más $$ 2^n f_4 (\frac12) = 2^n (\frac32)^{2n+1} = \frac32 (\frac92)^n \\= {2n+1 \elegir 2n+1}2^n + {2n+1 \elegir 2n}2^{n-1} + \cdots + {2n+1 \elegir n+1} + {\color{red}{ {2n +1 \elegir n} 2^{-1}+ \cdots + {2n +1 \elegir 0} 2^{n-1}}} $$ Las dos expresiones de la igualdad de $\frac32 (\frac92)^n$, y el primer $n+1$ muchos términos que representan el LHS y RHS de la pregunta original. Los términos en rojo son los términos adicionales: una vez que se estableció que estos términos también iguales, las preguntas se resuelve. Es decir, muestran que $$ \sum_{k=1}^{\infty}{2n +k \elegir n} 3^{-k} = \sum_{k=1}^{n+1}{2n +1 \elegir n+1-k} 2^{-k} $$