1
$\begingroup$

I am trying to find a closed form of the generating function $$\sum_{n\ge0} {n \choose k} \frac{x^n}{n!}$$ and I am not sure how to start. I have been going the other way, i.e., using generating functions to find closed forms of sequences, but not this way. Any help would be greatly appreciated.

$\endgroup$
4
$\begingroup$

Notice that

$$\binom nk\frac1{n!}=\frac1{k!(n-k)!}$$

And likewise, recall that

$$e^x=\sum_{n\ge0}\frac{x^n}{n!}$$

Differentiate both sides $k$ times to get

$$e^x=\sum_{n\ge k}\frac{x^{n-k}}{(n-k)!}$$

Now we can see that

$$\frac{x^ke^x}{k!}=\sum_{n\ge0}\frac{x^k}{k!(n-k)!}=\sum_{n\ge0}\binom nk\frac{x^n}{n!}$$

where we use the convention $\frac1{(-n)!}=0$ for natural $n$ greater than zero.

$\endgroup$
  • 1
    $\begingroup$ Thanks SBA ... I was about 30 seconds faster ... but your answer is more comprehensive :+) $\endgroup$ – Donald Splutterwit Mar 21 '17 at 0:34
3
$\begingroup$

Note that you need $n \ge k$, because ${n \choose k} = 0$ if $k > n$.

If $F_k(x)$ is your generating function, the generating function of these is

$$ \eqalign{\sum_{k=0}^\infty F_k(x) t^k &= \sum_{k=0}^\infty \sum_{n=k}^\infty {n \choose k} \frac{x^n t^k}{n!} \cr &= \sum_{n=0}^\infty \frac{x^n}{n!} \sum_{k=0}^n {n \choose k} t^k \cr &= \sum_{n=0}^\infty \frac{x^n}{n!} (1+t)^n = \exp(x(1+t)) \cr }$$ Thus $F_k(x)$ is the coefficient of $t^k$ in $\exp(x + xt)$, namely $$F_k(x) = \frac{x^k e^x}{k!}$$

$\endgroup$
3
$\begingroup$

Everyone has already written the obvious, simple solution, so let me write the hard-to-find, complicated solution.

In general, if $G(x) = \sum_{i\ge 0} g_i \frac{x^i}{i!}$ and $H(x) = \sum_{j\ge 0} h_j \frac{x^j}{j!}$, then $$G(x) H(x) = \sum_{i\ge0} \sum_{j\ge0} g_i h_j \frac{x^{i+j}}{i!\,j!} = \sum_{n \ge 0} \sum_{i+j=n} g_i h_j \frac{x^n}{i!\,j!} = \sum_{n \ge 0} \left(\sum_{i+j=n} \binom{n}{i} g_i h_j\right)\frac{x^n}{n!}.$$

In other words, if $G(x)$ is the e.g.f. for $(g_i)$ and $H(x)$ is the e.g.f. for $(h_j)$, then their product is the e.g.f. for the sequence $(p_n)$ where $$p_n = \sum_{i+j = n} \binom{n}{i} g_i h_j.$$

So if you want $p_n$ to be $\binom{n}{k}$ for some $k$ we can accomplish this by setting $$g_i = \begin{cases}1 & i = k\\0 & \mbox{else}\end{cases}$$ and setting $h_j=1$ for all $j$. If we do this, then $G(x) = \frac{x^k}{k!}$ and $H(x) = e^x$, so the generating function we want is $G(x) H(x) = \frac{x^k e^x}{k!}$.

$\endgroup$
  • 1
    $\begingroup$ This is upvoted because the identity being presented is very useful indeed, for more examples consult e.g. this MSE link I or this MSE link II. $\endgroup$ – Marko Riedel Mar 21 '17 at 2:02
2
$\begingroup$

Note that $ \binom{n}{k}=0$ when $ n < k $ ... so we can neglect the first $k$ terms. $ \binom{n}{k}=\frac{n!}{k! (n-k)!}$. We have \begin{eqnarray*} \sum_{n=k}^{\infty} \frac{x^{n}}{k!(n-k)!}= \frac{x^{k}}{k!}\sum_{n=k}^{\infty} \frac{x^{n-k}}{(n-k)!}= \color{red}{\frac{x^{k}}{k!}e^x} \end{eqnarray*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.