# How can I find the generating function of this sequence?

I am preparing for a test and I came across this example:

Find the closed form generating function of:

$$\dbinom{50}{1}, 2\dbinom{50}{2}, 3\dbinom{50}{3},..., 50\dbinom{50}{50},0,0,0,0$$

I know that I should use the binomial theorem and that:

$$G(x) = \sum_{k=0}^{49}(k+1)\dbinom{50}{k+1}$$

Can I cancel the two $(k+1)$'s. If so, can you explain it please?

EDIT: I made a mistake above, it should be: $$G(x) = \sum_{k=0}^{49}(k+1)\dbinom{50}{k+1}x^k$$ Since I need to find the generating function.

## 3 Answers

You have $$(k+1) \binom n {k+1} = (k+1) \frac{n!}{(k+1)!(n-k-1)!} =$$ $$= \frac{n!}{k!(n-1-k)!} = n \frac{(n-1)!}{k!(n-1-k)!}= n \binom{n-1} k$$ You then have $$\sum_{k=0}^{49} (k+1) \binom{50}{k+1} x^k = \sum_{k=0}^{49} 50 \binom{49}{k} x^k = 50 \cdot (1+x)^{49}$$ because $$\sum_{k=0}^n \binom n k x^k= (x+1)^n$$.

• Thanks, I think, however, that I made a mistake in my question to not include $x^k$ in the summation - since it is a generating function. Sorry about that – Julia Jul 19 '15 at 15:08
• You mean $G(x) = \sum_{k=0}^{49} (k+1) \binom{50}{k+1} x^k$? – Zardo Jul 19 '15 at 15:10
• Yes, see the edit in my question. – Julia Jul 19 '15 at 15:11
• I edited it! :) – Zardo Jul 19 '15 at 15:16

Yes, you can cancel. In general we have $\binom{n}{m}=\frac{n}{m}\binom{n-1}{m-1}$. This can be verified in various ways. For example we can operate mechanically, expressing the binomial coefficients in terms of factorials.

Thus $(k+1)\binom{50}{k+1}=(k+1)\cdot\frac{50}{k+1}\binom{49}{k}=50\binom{49}{k}$.

Another way: Write down the binomial expansion of $(1+x)^{50}$, differentiate term by term. One of many instances of a "new" generating function obtained from an old one by a close relative of (in this case) differentiation or integration.

You have that:

$$(1 + z)^{50} = \sum_{n \ge 0} \binom{50}{n} z^n$$

so that:

\begin{align} z \frac{\mathrm{d}}{\mathrm{d} z} (1 + z)^{50} &= \sum_{n \ge 0} n \binom{50}{n} z^n \\ &= 50 z (1 + z)^{49} \end{align}

which is the generating function you are looking for.