[BruceZ]

irchans,

I think a general formula could be difficult to find. There is another way to approach these problems using Fourier Series.

My solution is general in the sense that it gives a solution for all m,n,p and all the necessary terms are straightforward to compute. By general you mean F[n] = with no more reference to F[n] (no recursion). For that you would need to take the z-tranform (or generating function) of the difference equation, solve for F(z) = 1/(mth order polynomial in z), find all the roots of the polynomial, do a partial fraction expansion, and then invert the individual terms back to the n domain to get a sum of exponentials in n. For m=2, p=1/2 the roots are [ 1 +/- sqrt(5)] /2 as you found. It turns out that the real root always dominates, and this is what Feller's solution uses.

Is this what you mean by the Fourier series method? The z-transform is a general case of the discreet Fourier tranform. This is the technique I'm very familiar with.

I take it that mathematica doesn't spit out a result for general m? No closed form solution exists for factoring a general mth order polynomial, but it is not impossible that this particular family of polynomials could have a general solution.

I have found a non-recursive solution for F using only the single real root and a single term of F[n]. It is analogous to the reduced form of the Fibonacci solution.

BTW, since you will be looking at this closely, this line of the derivation:

= [ (1-p)/p ]*{ [ 1/(1-p) ]*t(n-1) – t(n-m-1) ]

uses a substitution from previous lines. This wasn't too obvious.

-Bruce