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.


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$$.

  • $\begingroup$ 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 $\endgroup$ – Julia Jul 19 '15 at 15:08
  • $\begingroup$ You mean $G(x) = \sum_{k=0}^{49} (k+1) \binom{50}{k+1} x^k$? $\endgroup$ – Zardo Jul 19 '15 at 15:10
  • $\begingroup$ Yes, see the edit in my question. $\endgroup$ – Julia Jul 19 '15 at 15:11
  • 1
    $\begingroup$ I edited it! :) $\endgroup$ – 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.


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.