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 ck(n), k, n = 0, 1, 2, …, satisfy

ck(n) = ck-1(n) + ck-1(n-k)

subject to the boundary conditions

c0(0) = 1 and c0(n) = 0 for all n=1, 2, …

I wanted to find a closed form expression for ck(n), but so far this has proved elusive. The first idea of using a two-variable generating function doesn’t work as the term ck-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 ck(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 ck(n) is extremely simple - it is

(1+x)(1+x2)…(1+xk)

Problem: find a closed form expression for ck(n).

About these ads

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

  1. Peter says:

    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

  2. Sacha says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: