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
Problem: find a closed form expression for ck(n).