I have come across a generating function that is similar to another generating function.

First, some preliminaries. I call a closed form a function like $\frac{1}{1-x}$. In other words, a closed form does not involve a summation or integral, but rather a bunch of arithmetic that describes a generating function.

Now, I have come across a closed form of the generating function:

$$\sum_{k=0}^\infty{X_k y^k} = X_0 + X_1 y^1 + X_2 y^2 + \dots$$

where the $X_k$'s are themselves generating functions:

$$X_k = \frac{1}{1-(z_k)} = 1 + (z_k) + (z_k)^2 + \dots$$

I'd like to convert the $X_k$'s into $z_k$'s. In other words, each coefficient of the original series is $\frac{1}{1-(z_k)}$. I'd like to convert from that to just $z_k$. I'm wondering if there is some sort of transformation that can do this all at once.

I would greatly appreciate any help on this.


I know how to get the $z$ values in the formula. What I really want is to change the formula into something that is not equal to the original formula. In other words, say I have:


Then I want:

$$y z_1 + y^2 z_2$$

  • $\begingroup$ Why not just substitute the formula you have for $X_k$ into the sum? You will get something like $$\sum_{k, l} z_k^l y^k$$ This is fairly messy, but I think it has to be that way, unless $z_k$ is something nice. $\endgroup$ – Jakub Konieczny Jan 26 '13 at 23:05
  • $\begingroup$ @Feanor: The problem is that I have a closed form. I start with something like $\displaystyle \frac{1}{1-y(\frac{1}{1-z})}$. This isn't the best example, but I really can't modify the individual $X_k$'s because the $z$'s are mixed together and are not in the form of a summation. I have everything in closed form, and that's my real problem. I'd like to modify the closed forms, if possible. $\endgroup$ – Matt Groff Jan 26 '13 at 23:20

Not all at once - don't worry about convergence, just substitute:

$\sum_{k=0}^\infty{X_k y^k} =\sum_{k=0}^\infty{\frac{ y^k}{1-z_k}} =\sum_{k=0}^\infty y^k\sum_{j=0}^\infty{z_k^j} = \sum_{j=0}^\infty \sum_{k=0}^\infty y^k {z_k^j} $.

From here on, it's up to you. If there is a more explicit form for the $z_k$, substitute it here and proceed.

  • $\begingroup$ I'm not sure that I can proceed like this. I'm actually trying to change the formula. I don't want $\sum{z_k}$ in the result. I want to transform $\sum{z_k} \to z_k$. $\endgroup$ – Matt Groff Jan 26 '13 at 23:26

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.