Binomial trees and a closed form expression for the terms of a recurrence relation

Recently, while playing with an integral of a probabilistic function possibly inspired by the binomial trees I’ve been reading about in financial mathematics books, I was attempting to find a closed form expression for the following recurrence relation:

Let c_{k}(n), k, n = 0, 1, 2, …, satisfy

c_{k}(n) = c_{k-1}(n) + c_{k-1}(n-k)

subject to the boundary conditions

c_{0}(0) = 1 and c_{0}(n) = 0 for all n=1, 2, …

I wanted to find a closed form expression for c_{k}(n), but so far this has proved elusive. The first idea of using a two-variable generating function doesn’t work as the term c_{k-1}(n-k) uses k, which varies throughout the two-variable generating function. From my reading about generating functions (I could easily be stood corrected on this), they can be used if, in the inductive definition, the new term is defined using other terms that are a constant “distance” away from the new term in the two-term generating function. The meaning of this should be clear to anyone who has played with generating functions.

In this problem, the new term is defined using terms that are not a constant “distance” away, and so you need to use a different approach (one that I havn’t yet discovered).

By searching for strings of integers given by c_{k}(n) for fixed values of k, I came across this webpage in the On-Line Encyclopedia of Integer Sequences, which gives information about this recurrence relation but no closed form expression. (The webpage coincidentally uses k and n but round the other way from how I use them.)

From that webpage (and a moment’s thought), the generating function for c_{k}(n) is extremely simple - it is

(1+x)(1+x^{2})…(1+x^{k})

Problem: find a closed form expression for c_{k}(n).

This entry was posted on Wednesday, May 30th, 2007 at 11:36 pm and is filed under Math and Physics. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

2 Responses to Binomial trees and a closed form expression for the terms of a recurrence relation

That generating function sounded familiar to me, unfortunately I cannot tell you anything in a positive manner about it. All I recall is Richard Stanley mentioning that to prove that the coefficients of that polynomial form a unimodal sequence (nondecreasing up to a point, then nonincreasing) is a difficult problem (that I have no idea how to do).

From the recursion relation, if you can prove that the coefficients of the polynomial are a nondecreasing sequence up to a point, it should be easy to show that the rest of them are a nonincreasing sequence (the sequence is just the mirror image of the nondecreasing sequence).

There might be no closed form expression giving the coefficients – if so, it’s interesting that the solution for a problem that looks so easy cannot be given by a closed expression.

That generating function sounded familiar to me, unfortunately I cannot tell you anything in a positive manner about it. All I recall is Richard Stanley mentioning that to prove that the coefficients of that polynomial form a unimodal sequence (nondecreasing up to a point, then nonincreasing) is a difficult problem (that I have no idea how to do).

Peter

Cheers Peter.

From the recursion relation, if you can prove that the coefficients of the polynomial are a nondecreasing sequence up to a point, it should be easy to show that the rest of them are a nonincreasing sequence (the sequence is just the mirror image of the nondecreasing sequence).

There might be no closed form expression giving the coefficients – if so, it’s interesting that the solution for a problem that looks so easy cannot be given by a closed expression.