3

The Full Question

Find the generating function(closed form) of the following sequence:

$\binom{8}{1},2\binom{8}{2},3\binom{8}{3},\dots , 8\binom{8}{8}$

My Work

The open form of this generating function is:

$1\binom{8}{1}x^0+2\binom{8}{2}x^2 +3\binom{8}{3}x^3 + \cdots +8\binom{8}{8}x^8$

This can be re-written as:

$0\binom{8}{0}x^0+1\binom{8}{1}x^0+2\binom{8}{2}x^2 +3\binom{8}{3}x^3 + \cdots +8\binom{8}{8}x^8$

Which in Sigma Notation is:

$\sum_{k=0}^{8}k\binom{8}{k}x^k$

Part of this series is obviously binomial, which has a closed form of $(1+x)^8$ I don't know how to deal with the $k$ that is always being multiplied in. I thought I could maybe use the multiplication rule for sums, but it doesn't seem to apply here because we have $a_1b_1$ instead of $a_1b_n$

My Problem

How do we deal with the k that is being multiplied in there constantly? How can I get a nice closed form generating function with that $k$ getting in my way?

user1176409
  • 1
Dunka
  • 2,787
  • 12
  • 41
  • 69
  • Note: Your sequences are off, in particular it should be $ { 8 \choose 1 } x^ 1 $? That sequencing affects whether I should multiply the answer by $x$ or not. – Calvin Lin Feb 16 '15 at 02:57

2 Answers2

2

Hint: $i { 8 \choose i } = 8 { 7 \choose i-1 } $

You should be able to quickly conclude that the generating function is

$ 8 ( 1 + x) ^ 7 x $

Calvin Lin
  • 68,864
1

Hint: Say the generating function is $ f(x)$. What do you know about $ \int \frac{f(x) - 8}{x} \, dx $?

Calvin Lin
  • 68,864
  • We haven't done any discussion of integration in class yet. My own integration is pretty rusty, so I put it in wolframalpha, which said there is no result in standard mathematical functions that it knows. Calculus wasn't listed as pre-req for this course either, is there a solution that doesn't involve calculus? – Dunka Feb 16 '15 at 02:00
  • @Dunka I added another solution, which makes a (magical) observation that leads to the answer. – Calvin Lin Feb 16 '15 at 02:53