Encontrar fórmulas utilizando funciones de generación

Question

Quiero encontrar la suma: $$\sum \limits_{k=0}^n {n\choose k}2^{k-n}$$

Yo lo hice usando el teorema del binomio y tengo

$$\sum \limits_{k=0}^n {n\elegir k}2^{k-n} = 2^{n} \sum \limits_{k=0}^n {n \elegir k}2^k = \left(\frac{1}{2}\right)^n3^n$$

Me gustaría saber cómo hacerlo mediante la generación de funciones. He probado algunos cálculos, pero estoy atascado. Esto es lo que tengo hasta ahora.

$$\sum \limits_{k=0}^n {n\elegir k}2^{k-n} =\sum \limits_{n\ge0} \sum \limits_{k\ge0} {n \elegir k} 2^{k-n} x^n =\sum \limits_{k\ge0} 2^k \sum \limits_{n\ge0} {n \elegir k}\left(\frac{x}{2}\right)^n$$

Answer 1

El coeficiente binomial en $\sum \limits_{k=0}^n \binom{n}{k}2^{k-n}$ indica que se podría utilizar la de Cauchy-producto de exponenciales funciones de generación. Tenemos \begin{align*} A(x)=\sum_{k=0}^\infty a_k\frac{x^k}{k!},\ \ B(x)=\sum_{l=0}^\infty b_l\frac{x^l}{l!}\quad\longleftrightarrow\quad A(x)B(x)=\sum_{n=0}^\infty \left(\sum_{k=0}^n\binom{n}{k}a_kb_{n-k}\right)\frac{x^n}{n!} \end{align*}

Obtenemos \begin{align*} \sum_{n=0}^\infty\left(\color{blue}{\sum_{k=0}^n\binom{n}{k}2^{k-n}}\right)\frac{x^n}{n!} &=\sum_{n=0}^\infty\left(\sum_{k=0}^n\binom{n}{k}1^k\left(\frac{1}{2}\right)^{n-k}\right)\frac{x^n}{n!}\\ &=\left(\sum_{k=0}^\infty\frac{x^k}{k!}\right)\left(\sum_{l=0}^\infty\frac{\left(\frac{x}{2}\right)^l}{l!}\right)\\ &=e^xe^{\frac{x}{2}}\\ &=e^{\frac{3}{2}x}\\ &=\sum_{n=0}^\infty\color{blue}{\left(\frac{3}{2}\right)^n}\frac{x^n}{n!} \end{align*} y el reclamo de la siguiente manera.

Además el método más común por encima también tenemos la posibilidad de uso ordinario de la generación de funciones. Se puede aplicar una transformación conocida como Euler transformación de una serie \begin{align*} A(x)=\sum_{n= 0}^\infty a_nx^n\quad\longrightarrow\quad \frac{1}{1-x}A\left(\frac{x}{1-x}\right)=\sum_{n= 0}^\infty \left(\sum_{k=0}^n\binom{n}{k}a_k\right)x^n \end{align*} Esta transformación de la fórmula, junto con una prueba se puede encontrar por ejemplo, en el Número Armónico de las Identidades a Través de Euler transformar por K. N. Boyadzhiev (ver Lema 1).

Obtenemos \begin{align*} \sum_{n=0}^\infty\left(\color{blue}{\sum_{k=0}^n\binom{n}{k}2^{k-n}}\right)x^n &=\sum_{n=0}^\infty\left(\sum_{k=0}^n\binom{n}{k}2^k\right)\left(\frac{x}{2}\right)^n\\ &=\frac{1}{1-\frac{x}{2}}\sum_{n=0}^\infty2^n\left(\frac{\frac{x}{2}}{1-\frac{x}{2}}\right)^n\\ &=\frac{1}{1-\frac{x}{2}}\cdot\frac{1}{1-2\left(\frac{\frac{x}{2}}{1-\frac{x}{2}}\right)}\\ &=\frac{1}{1-\frac{3}{2}x}\\ &=\sum_{n=0}^\infty\color{blue}{\left(\frac{3}{2}\right)^n}x^n \end{align*} y el reclamo de la siguiente manera.

Answer 2

Usted tiene $$ \eqalign{ & \sum\limits_{0\, \le \,k\, \le \,n} {\left( \matriz{ n \cr k \cr} \right)2^{\,k - n} } = \sum\limits_{0\, \le \,k\, \le \,n} {\left( \matriz{ n \cr k \cr} \right)\left( {{1 \over 2}} \right)^{\,n - k} } = \sum\limits_{0\, \le \,k\, \le \,n} {\left( \matriz{ n \cr k \cr} \right)\left( {{1 \over 2}} \right)^{\,n - k} } 1^{\,k} = \cr & = \left( {{1 \over 2} + 1} \right)^{\n} \cr} $$ o, si lo prefiere $$ \sum\limits_{0\, \le \,k\, \le \,n} {\left( \matriz{ n \cr k \cr} \right)z^{\,k - n} } = z^{\, - n} \sum\limits_{0\, \le \,k\, \le \,n} {\left( \matriz{ n \cr k \cr} \right)z^{\,k} } = {{\left( {z + 1} \right)^{\n} } \over {z^{\n} }} $$

Answer 3

Otro de mirar el problema, usando el hecho de que $${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}}$$ podemos construir la relación de recurrencia para la secuencia: $$a_n=\sum \limits_{k=0}^n {n\elegir k}2^{k-n}= {n\elegir 0}2^{-n}+\sum \limits_{k=1}^{n-1} {n\elegir k}2^{k-n}+{n\elegir n}2^{0}=\\ {n\elegir 0}2^{-n}+\sum \limits_{k=1}^{n-1} \left({n-1\elegir k-1}+{n-1\elegir k}\right)2^{k-n}+{n\elegir n}2^{0}=\\ {n\elegir 0}2^{-n}+\sum \limits_{k=1}^{n-1} {n-1\elegir k-1}2^{(k-1)-(n-1)}+\sum \limits_{k=1}^{n-1}{n-1\elegir k}2^{k-n}+\color{red}{{n\elegir n}2^{0}}=\\ \color{blue}{{n\elegir 0}2^{-n}}+\sum \limits_{k=0}^{n-2} {n-1\elegir k}2^{k-(n-1)}+\color{red}{{n-1\elegir n-1}2^{0}}+\sum \limits_{k=1}^{n-1}{n-1\elegir k}2^{k-n}=\\ a_{n-1}+\color{blue}{\frac{1}{2}{n-1\elegir 0}2^{-(n-1)}}+\frac{1}{2}\sum \limits_{k=1}^{n-1}{n-1\elegir k}2^{k-(n-1)}=\\ a_{n-1}+\frac{1}{2}a_{n-1}=\frac{3}{2}a_{n-1}$$ Esta recurrencia puede ser resuelto por la inducción, el uso de funciones de generación o característica de polinomios.

Con funciones de generación, dado $a_0=1$ $$f(x)=a_0+\sum\limits_{n=1}a_nx^n=1+\frac{3}{2}x\sum\limits_{n=1}a_{n-1}x^{n-1}=\\ 1+\frac{3}{2}x\sum\limits_{n=0}a_{n}x^{n}= 1+\frac{3}{2}xf(x)$$ que conduce a la $$f(x)=\frac{1}{1-\frac{3}{2}x}=\sum\limits_{n=0}\color{red}{\left(\frac{3}{2}\right)^n}x^n$$