# Numerical Determination of Generating Functions from Recursion Relations

Are there computer packages which calculate coefficients of generating functions, such as

$$D_n(q)=\sum_m d_{m,n}q^m= \frac{1}{\prod_{i=1}^n (1-q^i)^2} \text{ or}$$

$$S_d(q)=\sum_m s_{m,d}q^m = \frac{q^d}{\prod_{i=1}^d (1-q^i)} \; ?$$

The effort, to calculate all coefficients e.g. $d_{k,l}$ for $k$ and $l$ smaller than $N$ should grow with $N^3$, as they satisfy recursion relations such as

$$d_{m,n} = \sum_{k=0}^{[m/n]}(k+1)d_{m-k\cdot n,n-1}$$

which allow to express each of the $N^2$ coefficients as a sum of at most $N$ terms ($d_{m,1}=m+1$, $d_{0,0}=1$, $d_{m,0}=0$ for $m>0$).

Before I revive my rusty computer knowledge I would like to know whether computer packages such as GAP tackle my problem to solve recursion relations with given initial conditions, save the solutions to files and allow to read them in again if one wants to tackle the next case $N+1$.

• Your LaTeX was not displayed properly for two reasons: enclosing something with backticks makes it code, and MathJax cannot parse it: for eg, $H$. If you want to see H, you'd say $H$. Also, to center the display, it is best to enclose the equation by double dollars. Do not have a number of spaces in the beginning of a line. Any line that begins with four space is treated as code and once again, MathJaX cannot parse it. – knsam Jun 27 '13 at 20:19
• @knsam I approved the edit and only made a slight change to display the formulas more compactly, including the 'or' in the same line and avoiding a 'lonely' questionmark. – user9072 Jun 27 '13 at 20:24
• Regarding the question itself, AFAIK, sage itself does not do generating functions per se; but, in this context, I can see a much simpler algorithmic code, which is based on the observation that I can truncate $(1 - q^i)^{-1}$ after a certain index that is an easy-to-figure function of $m$. So, there are ways to handle this, but, thinking of them as generating functions as such is not going to help make matters nice. – knsam Jun 27 '13 at 23:00
• @qknsam: Isn't the truncation which you suggest the content of the recursion relation, $D_n(q) = (1-q^n)^{-2} D_{n-1}(q)$, $(1-q^n)^{-2}=\sum_k (k+1)q^{k\cdot n}$ ? – Norbert Dragon Jun 28 '13 at 12:02
• I know I have used Maple to calculate similar things, but as I am currently without Maple access I can't test it for you. – Gerry Myerson Jul 1 '13 at 6:13

Check out Bruno Salvy (et al's) gfun package.

In Maple you can do

series(mul((1-q^i)^(-2),i=1..10),q=0,1000)


to get $D_{10}(q)$ as far as $q^{999}$; this took 0.9 seconds on my laptop. Alternatively, you can do

d := proc(m,n)
option remember;

if n = 0 then
if m = 0 then
return 1;
else
return 0;
fi;
else

This calculates $d(1000,10)$ in about 0.9 seconds again. It remembers all instances of $d(m,n)$ that it has already computed.