Find a close formula using generating functions

Question

I want to find the sum: $$\sum \limits_{k=0}^n {n\choose k}2^{k-n}$$

I did it by using the binomial theorem and I got

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

I would like to know how to do it using generating functions. I have tried some calculations but I am stuck. This is what I have so far.

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

Answer 1

Another look at the problem, using the fact that $${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}}$$ we can construct the recurrence relation for the sequence: $$a_n=\sum \limits_{k=0}^n {n\choose k}2^{k-n}= {n\choose 0}2^{-n}+\sum \limits_{k=1}^{n-1} {n\choose k}2^{k-n}+{n\choose n}2^{0}=\\ {n\choose 0}2^{-n}+\sum \limits_{k=1}^{n-1} \left({n-1\choose k-1}+{n-1\choose k}\right)2^{k-n}+{n\choose n}2^{0}=\\ {n\choose 0}2^{-n}+\sum \limits_{k=1}^{n-1} {n-1\choose k-1}2^{(k-1)-(n-1)}+\sum \limits_{k=1}^{n-1}{n-1\choose k}2^{k-n}+\color{red}{{n\choose n}2^{0}}=\\ \color{blue}{{n\choose 0}2^{-n}}+\sum \limits_{k=0}^{n-2} {n-1\choose k}2^{k-(n-1)}+\color{red}{{n-1\choose n-1}2^{0}}+\sum \limits_{k=1}^{n-1}{n-1\choose k}2^{k-n}=\\ a_{n-1}+\color{blue}{\frac{1}{2}{n-1\choose 0}2^{-(n-1)}}+\frac{1}{2}\sum \limits_{k=1}^{n-1}{n-1\choose k}2^{k-(n-1)}=\\ a_{n-1}+\frac{1}{2}a_{n-1}=\frac{3}{2}a_{n-1}$$ This recurrence can be solved by induction, using generating functions or characteristic polynomials.

With generating functions, given $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)$$ leading to $$f(x)=\frac{1}{1-\frac{3}{2}x}=\sum\limits_{n=0}\color{red}{\left(\frac{3}{2}\right)^n}x^n$$

Answer 2

You have $$ \eqalign{ & \sum\limits_{0\, \le \,k\, \le \,n} {\left( \matrix{ n \cr k \cr} \right)2^{\,k - n} } = \sum\limits_{0\, \le \,k\, \le \,n} {\left( \matrix{ n \cr k \cr} \right)\left( {{1 \over 2}} \right)^{\,n - k} } = \sum\limits_{0\, \le \,k\, \le \,n} {\left( \matrix{ n \cr k \cr} \right)\left( {{1 \over 2}} \right)^{\,n - k} } 1^{\,k} = \cr & = \left( {{1 \over 2} + 1} \right)^{\,n} \cr} $$ or, if you prefer $$ \sum\limits_{0\, \le \,k\, \le \,n} {\left( \matrix{ n \cr k \cr} \right)z^{\,k - n} } = z^{\, - n} \sum\limits_{0\, \le \,k\, \le \,n} {\left( \matrix{ n \cr k \cr} \right)z^{\,k} } = {{\left( {z + 1} \right)^{\,n} } \over {z^{\,n} }} $$

Answer 3

The binomial coefficient in $\sum \limits_{k=0}^n \binom{n}{k}2^{k-n}$ indicates that we could use the Cauchy-product of exponential generating functions. We have \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*}

We obtain \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*} and the claim follows.

Besides the more common method above we also have the possibility to use ordinary generating functions. We can apply a transformation known as Euler transform of a series \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*} This transformation formula together with a proof can be found e.g. in Harmonic Number Identities Via Euler's transform by K.N. Boyadzhiev (see Lemma 1).

We obtain \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*} and the claim follows.