Recursion Puzzle With Binomial Coefficients

Let a(0,m) = 1 (for every positive integer m).

For n = nonnegative integers, m = positive integers,

let a(n+1,m) =

m * sum{k=1 to m} a(n,k) binomial(m+n,k+n) (-1)^(k+1) /k.

In ascii-art mode:

a(n+1,m) = m

On 18 Oct 2002, Leroy Quet wrote:

Is there anything unusually simple or puzzle-like about the solution? A Maple worksheet generating my partial solution (for m <= 19) is available at http://groups.yahoo.com/group/meg-sugarbush/files/ as file RecPuzzlesLeroy.mws, and a JPEG of a log plot of the solution for n <= 40, m <= 19 is viewable in the same directory as RecPuzzlesLeroy.jpg. This uses my 3-dimensional logarithmic plotting package for Maple available at http://www.mapleapps.com.

P A R T I A L

S P O I L E R

Solve recursively for each fixed m starting with m=1. We get a first-order linear recurrence with polynomial forcing functiom, hence it is easy to solve.

For each m, I get a[m](n) = p[m](n) - (-1)^n * q[m](n) where p[m] is a polynomial of degree m-1 and q[m] is a polynomial of degree m-2.

p[1] = 1 q[1] = 0

p[2] = n+3/2 q[2] = 1/2

p[3] = 3/8*n^2 + 15/8*n + 31/16 q[3] = 3/8*n + 15/16

Maybe you are seeing a pattern in the coefficients at this point, but...

p[4] = n^3/12 + 7/8*n^2 + 65/24*n + 7/3 q[4] = 1/8*n^2 + 7/8*n + 4/3

p[5] = 5/384*n^4 + 15/64*n^3 + 185/128*n^2 + 225/64*n + 691/256 q[5] = 5/192*n^3 + 45/128*n^2 + 275/192*n + 435/256

Just giving the coefficients now to save space, from highest degree to lowest degree: p[6] = 1/640 11/256 169/384 33/16 16523/3840 1947/640 q[6] = 1/256 11/128 21/32 517/256 1307/640

Now putting over a common denominator (cd)

p[7]= 14 546 8365 63700 250089 467558 310287 q[7]= 42 1365 16660 94185 241766 218127 cd[7]= 92160

p[8]= 2 105 2247 25200 158179 546840 940131 592920 q[8]= 7 315 5600 49875 231672 521955 431640 cd[8]= 161280

p[9]= 6 408 11620 179928 1643530 8970696 28130380 45223944 27339675 q[9]= 24 1428 34776 446250 3229128 13010508 26521608 20458395 cd[9]= 6881280

What is the pattern?

V

V

V

V

V

For n >= 1,

a(n,m) =

m *binomial(ceiling(n/2)+m-1,m) *sum{j=1 to m} 1/(j+ceiling(n/2)-1)

In other words:

a(2n-1,m) = a(2n,m) =

m *binomial(n+m-1,m) *sum{j=1 to m} 1/(j+n-1)

In still other words:

a(2n-1,m) = a(2n,m) =

m *H(n,m),

where H(0,m) = 1/m, and H(n,m) = sum{k=1 to m} H(n-1,k), a higher-order harmonic number. Though I consider this form for a(n,m) to be a 'closed-form', the form involving the binomial coefficient is 'more' closed in most people's opinion, I would presume.

Thanks, Leroy Quet