## Generating functions - (1-x-x^2-x^3-x^4-x^5-x^6)^-1

Math Help on Kolmogorov axioms, Measure Theory, Sigma Algebra, Probability Space, Random variables, Random vectors, Expectation, Variance, Standard Deviation, Weak convergence; Convergence in Law, in Probability, Almost surely, Everywhere; the weak and the strong Law of Large Numbers, the Central Limit theorem, Tests, Samples, Confidence Intervals, Estimators, Consistence, Parametric and Non-parametric Statistics on My Math Forum.
Math problems in Probability

### Generating functions - (1-x-x^2-x^3-x^4-x^5-x^6)^-1

Hi all!

I've got this problem here:
Show that (1 - x - x^2 - x^3 - x^4 - x^5 - x^6)^-1 is the generating function for the number of ways a sum of r can occur if a die is rolled any number of times.

It's a homework problem, but it's past due, so I am just trying to figure it out because I think I may have missed something important that I need to solve this.

I was able to solve this with recurrence relations:
C0 = 1 (there is 1 way to roll a sum of 0), and CN = CN-1 + CN-2 + CN-3 + CN-4 + CN-5 + CN-6.
I used that to get h(x) - x - 2x^2 - 4x^3 - 8x^4 - 16x^5 - 32x^6 = x (h(x) - x - 2x^2 - 4x^3 - 8x^4 - 16x^5) + x^2 (h(x) - x - 2x^2 - 4x^3 - 8x^4) + x^3 (h(x) - x - 2x^2 - 4x^3) + x^4 (h(x) - x - 2x^2) + x^5 (h(x) - x) + x^6 (h(x)), where g(x) = h(x) + 1, because h(x) does not include the 1 * x^0 term. This works out fine.

But there should be some way to verify this without recurrence relations. I'm not sure how to convert the generating function to a sum, or how to reconstruct (build) the generating function, but there should be some way to do either of those.

Hopefully someone here can give some advice.
Thanks.
KristopherWindsor
Newcomer

Posts: 3
Joined: Sat May 01, 2010 6:02 am

### Re: Generating functions - (1-x-x^2-x^3-x^4-x^5-x^6)^-1

Taylor expansion $\frac{1}{1-X-X^2-X^3-X^4-X^5-X^6}=$
$1 + X + 2 X^2 + 4 X^3 + 8 X^4 + 16 X^5 + 32 X^6 + 63 X^7 + 125 X^8 + 248 X^9 +\cdots$
(Sloane's A001592)

$\sum_{j=1}^{\infty}\left(\sum_{i=1}^{6}x^i\right)^j\\$
Xitami
Queen of Hearts

Posts: 65
Joined: Tue Apr 13, 2010 8:15 pm

### Re: Generating functions - (1-x-x^2-x^3-x^4-x^5-x^6)^-1

Now I understand that this is the generating function for the problem:
$\sum_{j=1}^{\infty}\left(\sum_{i=1}^{6}x^i\right)^j\\$
And I understand that it expands like this:
$1 + X + 2 X^2 + 4 X^3 + 8 X^4 + 16 X^5 + 32 X^6 + 63 X^7 + 125 X^8 + 248 X^9+\cdots$

But I'm not quite sure how to convert between that and $\frac{1}{1-X-X^2-X^3-X^4-X^5-X^6}=$.
Thanks.
KristopherWindsor
Newcomer

Posts: 3
Joined: Sat May 01, 2010 6:02 am

### Re: Generating functions - (1-x-x^2-x^3-x^4-x^5-x^6)^-1

Do you know the power series expantion for $\frac{1}{1-Y}$ in powers of Y ?

g_edgar
King of Diamonds

Posts: 150
Joined: Sat Jun 27, 2009 9:23 am

### Re: Generating functions - (1-x-x^2-x^3-x^4-x^5-x^6)^-1

Well, I understand this:

But I'm not sure how it relates to $\frac{1}{1-Y-Y^2}$, $\frac{1}{1-Y-Y^2-Y^3}$, etc.
Again, I'm not exactly sure what I'm missing here. :S

I'm not sure how to show this:
$\frac{1}{1-X-X^2-X^3-X^4-X^5-X^6}=\sum_{j=1}^{\infty}\left(\sum_{i=1}^{6}x^i\right)^j\\$

It'd be nice if you could explain that.
KristopherWindsor
Newcomer

Posts: 3
Joined: Sat May 01, 2010 6:02 am