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 Answers 4

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
  • 1
    $\begingroup$ Thanks SBA ... I was about 30 seconds faster ... but your answer is more comprehensive :+) $\endgroup$ Mar 21, 2017 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
  • 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$ Mar 21, 2017 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$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .