A recursive Double sequence related to uniform Cardinal B-spline

Question

Given a sequence $A_n(k)$ defined as follows:

$A_0(0)=1$, $A_0(k)=0$ for all nonzero integers $k$ and $$A_{n}(k)=(n+1-k)^2A_{n-1}(k-1)+2(n(n+1)-k^2)A_{n-1}(k)+(n+1+k)^2A_{n-1}(k+1)$$ for all positive integers $n$ and (positive or negative) integers $k$. Does there exist an explicit formula for $A_n(k)$? This sequence is related to the function values of the uniform cardinal B-splines at the integers.

Thanks for any help in advance

Markus

Answer 1

Edit: ok, now that I have more than 5 minutes to spare I can clean this up a bit and add a wikipedia reference.

I'm going to write A(n,k) for $A_n(k)$. First of all, note that it's easy to see that A(n,k) = A(n,-k) by induction on n, and that the A(n,k) are zero unless -n <= k <= n. So we may as well just start computing these things (with dynamic programming, for good practice) before we start thinking terribly hard:

Sage code:

values = {}
def A(n,k):
    if (n,k) in values:
        return values[(n,k)]
    if n==0:
        if k==0:
            result = 1
        else:
            result = 0
    else:
        result =  (n + 1 - k)**2 * A(n-1, k-1)
        result += 2*(n*(n+1)-k**2) * A(n-1, k)
        result += (n + 1 + k)**2 * A(n-1, k+1)
    values[(n,k)]=result
    return result

for n in range(5):
    print [A(n,k) for k in range(-n, n+1)]

Output:

[1]
[1, 4, 1]
[1, 26, 66, 26, 1]
[1, 120, 1191, 2416, 1191, 120, 1]
[1, 502, 14608, 88234, 156190, 88234, 14608, 502, 1]

One glance at the third row will tell any combinatorist that these are Eulerian numbers (at least, for odd n). See sequence A008292 at oeis.org. Also, wikipedia has a perfectly reasonable page on the Eulerian numbers: http://en.wikipedia.org/wiki/Eulerian_number. There you can find a recursive formula. I'll use E(n,m) since A is taken already:

$E(n,m) = (n-m)E(n-1,m-1) + (m+1)E(n-1,m)$.

Of course this notation is different than yours; I think your numbers are $E(2n+1, m-n)$, You should be able to see this by applying the above recursive formula twice and doing the above change of variables to recover your own formula, though I haven't done it and may have made an error. There's lots of formulas for the Eulerian numbers and there's a lot known about them.