# Transform recursion for coefficients into differential equation for generating function

Assume, one is given a linear recursion with polynomial coefficients for a sequence $(a_i)_i$, such as

a[i] == i a[i-1]


I would like to convert this recursion into a differential equation for the (formal) generating function $G(x)=\sum_{i}a_i x^i$.

In my example above, direct manipulation leads me to the equation $$G(x)=2x^2 a_1+x^2 G'(x)+xG(x)$$ which Mathematica can solve in terms of special functions. Interestingly, the power series with coefficients $i!$ (the solution to $a_i=i a_{i-1}$) doesn't converge for any $x$. Since I'm only interested in formal power series, however, I still believe that my question makes sense.

I'm particular interested in a method that also works for higher order recursions with higher degree polynomial coefficients.

Thanks.

I would like to add that I am familiar with the functions GeneratingFunction[] and RSolve[] but neither seems to be of much help for this problem.

Edit 18 April 2014: In version 9 the behaviour of GeneratingFunction appears to have changed in such a way that it doesn't directly solve this problem any longer. I therefore reactivate this question and ask for a way to transform a linear recursion with polynomial coefficients into a differential equation for the generating function.

• GeneratingFunction[] does what I want. Apparently I wasn't sufficiently familiar with this function after all. – Eckhard Aug 26 '13 at 17:40

The usual approach for problems like these is to combine GeneratingFunction[] (as already noted by the OP) with DifferenceRoot[], as in the following:

GeneratingFunction[DifferenceRoot[Function[{a, k}, {a[k] == a[k - 1]/k, a[0] == 1}]][k],
k, x]
DifferentialRoot[Function[{y, x}, {-y[x] + y'[x] == 0, y[0] == 1}]][x]


after which one can use FunctionExpand[]:

FunctionExpand[%]
E^x


However, for the OP's specific case involving the exponential integral, GeneratingFunction[] refuses to budge at all, even after setting VerifyConvergence -> False. One possible recourse is to directly construct the regularized sum:

Sum[DifferenceRoot[Function[{a, k}, {a[k] == k a[k - 1], a[0] == 1}]][k] x^k,
{k, 0, ∞}, Regularization -> "Borel"]
-((E^(-1/x) Gamma[0, -(1/x)])/x)


and then you can use DifferentialRootReduce[] to see the associated ODE:

DifferentialRootReduce[%, x]
DifferentialRoot[Function[{y, x}, {y[x] + (-1 + 3 x) y'[x] + x^2 y''[x] == 0,
y[1] == -(Gamma[0, -1]/E), y'[1] == 1}]][x]


Note that the initial conditions were not placed at $$x=0$$ even if the function is actually well-defined there.

Beware of "formal power series" of this type. I have an example of a very competent mathematics professional that led him into ?? land. Concerning your question let's look at the condition $a_0=0\cdot a_{-1}$ which is off the end but doesn't matter because it sets $a_0 = 0$

But by recursion this sets all

$a_x = 0$

So the relation can only be non-trivially true for i>0. BTW: direct calculation doesn't seem to need $2x^2a_1$ In other words.

$G(x)-x^2 G'(x)-xG(x)$ seems to be zero. Gathering the $x^i$ terms $a_i x^i - x^2 x^{i-2} a_{i-1}(i-1) - x^1 x^{i-1} a_{i-1} = a_i x^i - i a_{i-1}x^i$

Which is the requirement. Adding another term makes in non-homogenious. In addition evaluating the left and right hand sides for $x^2$ gives

$a_2 x^2 = 2a_1 x^2 +a_1 x^2 + a_1 x^2$ $a_2 = 4 a_1$ together with $a_2=2a_1$ Doesn't work! Unless you start the recursion at i>2.

Sorry for being a little "long winded"