A recurrence

[Max]

Consider an E.G.F. for the sequence ss(n):

F(x,y) = SUM[n=0..oo] s(n)*y^n / n!

The given recurrence relation implies that the function F(x,y)
satisfies the following differential equation:

(y+1) * dF(x,y)/dy = (y-x-1) * F(x,y)
F(x,0) = 1

implying F(x,y) = exp(y) / (y+1)^(x+2).

Now it easy to get ss(n) as a coefficient of y^n in F(x,y) multiplied by n!:

ss(n) = n! * SUM[k=0..n] binomial(-x-2,k) / (n-k)!

This formula can be implemented in PARI as

ss(n)=n!*sum(k=0,n,binomial(-x-2,k)/(n-k)!)

For example, for n=0..10 we get the following values:
? vector(11,n,ss(n-1))
%1 = [1, -x - 1, x^2 + 3*x + 3, -x^3 - 6*x^2 - 14*x - 11, x^4 + 10*x^3
+ 41*x^2 + 76*x + 53, -x^5 - 15*x^4 - 95*x^3 - 305*x^2 - 489*x - 309,
x^6 + 21*x^5 + 190*x^4 + 925*x^3 + 2524*x^2 + 3623*x + 2119, -x^7 -
28*x^6 - 343*x^5 - 2345*x^4 - 9569*x^3 - 23121*x^2 - 30414*x - 16687,
x^8 + 36*x^7 + 574*x^6 + 5236*x^5 + 29659*x^4 + 106148*x^3 +
233050*x^2 + 285360*x + 148329, -x^9 - 45*x^8 - 906*x^7 - 10626*x^6 -
79527*x^5 - 391839*x^4 - 1264934*x^3 - 2567778*x^2 - 2959881*x -
1468457, x^10 + 55*x^9 + 1365*x^8 + 20010*x^7 + 190953*x^6 +
1234233*x^5 + 5450255*x^4 + 16172450*x^3 + 30735111*x^2 + 33635507*x +
16019531]

btw, the sequence of free terms in ss(n) (in absolute value) is given
by A000255, i.e.:
1, 1, 3, 11, 53, 309, 2119, 16687, 148329, 1468457, 16019531, ...

Max

On 5/27/06, Brendan McKay <bdm at cs.anu.edu.au> wrote:
> Anyone know how to solve recurrences like this?
>
> s(0) = 1
> s(1) = -x-1
> s(i) = (i-1)*ss(i-2) - (i+x)*ss(i-1)   (i >= 2)
>
> For example:
> s(2) = x^2+3x+3
> s(3) = -x^3-6x^2-14x-11
>
> Thanks, Brendan.
>


MIME-Version: 1.0