I’ve run into a recurrence relation that I’m having a bit of trouble solving. It defines a function, C in N[sup]2[/sup] -> N as follows:
C(n, 0) = C(n, n) = n + 1
C(n, k) = 2(C(n - 1, k) + C(n - 1, k - 1) - 1), 0 < k < n
C(n, k) = 0, n < k
All the references I can find discuss solving single-variable recurrence relations, and most of them are restricted to linear homogeneous ones. That ain’t this.
Do we know anything about how to solve something like this? Or is it best to just start coding up a little dynamic programming to be able to compute values quickly?
write down the first few rows on a piece of paper and you will see it.
Let me know if you need a formal proof for this. I cannot promise anything, but I would give it a try. Induction should work, now that we have the solution.
That doesn’t work for n = 3, and definitely doesn’t work for the boundaries.
I’m not so much interested in the solution as the method of finding it. I’m hoping that there’s something more reliable than guess and check for this sort of problem.
Sorry, I missed the boundary conditions (somehow I just read C(0,0) = 1 for getting started) and the “-1” in the formula for the general case, which makes the whole thing lopsided. I’m getting tired.
In general, no, there is no clear road to the solution. You nose around a bit, guess something, test your would-be solution for some interesting cases, then you try to prove it by induction.
In theory, you could also try to embed this discrete problem into a continuous one and get some differential equations to solve, but that would be difficult enough even without boundary conditions that contradict the rules for the other elements.
The only exact approach I know is to use generating functions. “Concrete Mathematics” is the best resource for solving these usings gfs that I know of.
Since I’m a CS guy, I do Big Oh analysis of such things which is a whole lot easier in many cases. (Work out the first few numbers, take a stab, try an induction proof, see where it goes wrong, fix the problem, lather, rinse repeat.) But given the likelyhood of binomials in the answer, even that might not work.
If you work out the numbers for a few nontrivial columns, then try the online integer sequence database to see if someone has already noted them, which could give you some good leads.
I agree with ftg that generating functions are a convenient general attack on linear recurrence relations. This particular case is made rather nasty by the ugly choice of boundary conditions (and the inhomogeneity of the recursion), though. The problem is that the recursion relation is not trivially satisfied at the boundary (k=0 or k=n), unlike the superficially-similar case of the binomial coefficients (in which by defining (n choose k) = 0 for k<0 or k>n, the recursion relation (n+1 choose k) = (n choose k) + (n choose k-1) holds for all k). This makes writing down the differential equation for the generating function pretty ugly.
Here’s a second way of thinking about the problem (this is just a sketch; I’m not trying to be rigorous). First, let’s make the obvious redefinition to remove the inhomogeneity: Define
D(n,k) = C(n,k) - 2/3
so that D(n,k) is defined by the recursion
D(n+1,k) = 2[D(n,k) + D(n,k-1)] (for 0 < k < n),
with boundary conditions
D(n,0) = D(n,n) = n + 1/3 .
Now let’s change the problem a little bit, just for fun. Define G(n,k) by the recursion
G(n+1,k) = 2[G(n,k) + G(n,k-1)] (for all k, and for n>0)
with boundary conditions
G(0,0) = 1
G(0,k) = 0, k != 0.
Clearly G(n,k) = 2[sup]n[/sup] (n choose k) for n >= 0. But, because G and D have the same recursion relation within the region of interest, we can think of G(n,k) as a Green’s function for D(n,k), as long as we make the correct choice of boundary conditions. So D(n,k) is just a sum over G(n-n’,k-k’), weighted appropriately.
Here is where it gets ugly (and I don’t know if there’s an elegant solution). The boundary condition for G is a Kronecker delta along a constant-n slice; the recursion relation then gives us nonzero values for G within the “octant” 0 <= k <= n. Because D is explicitly specified along the boundary of this octant, the boundary conditions cannot be thought of as independent (relative to this G). Each boundary condition for a given n will contribute to the boundary values for all n’ > n; these contributions must then be subtracted out before using the larger values as sources. I haven’t worked out these corrections, though, so I don’t know if they’re analytically tractable.
FWIW, I was able to get a single-sum solution using this Green’s function. The sum for D(n,k) (and therefore C(n,k)) has O(n) terms, so it’s better than a naive recursion on the defining equation (which has O(n[sup]2[/sup]) terms), but not as good as a lookup+recursion if you’re computing Omega(n) values; I haven’t found a closed form for the sum though.
Finding a generating function for this relation is actually a tedious (but easy, step-by-step) algebra problem. I didn’t want to post until I had an answer, which I worked out on the plane yesterday.
I don’t know of one offhand. What I’ve used is pretty simply to transcribe, though. \le is less-than-or-equal, \frac{a}{b} is the fraction a/b, \Sum is a sigma, _ and ^ denote sub- and superscripts, and scripts longer than a single character are in braces.
Incidentally, Maple has tools to find a closed form for one variable, but not two. If you could find some Maple code that handled that, you could try cranking through.
Try MiKTeX. It comes bundled with a DVI viewer and converters dvips/dvipdf* to get PostScript/PDF.
If you try it with Mathochist’s reply above, note the following typos:
[ul][li]there’s an extra closing brace } near the end of the final line of the first equation array (just after the x^iy^j[/li][li]the "\Sum"s should be “\sum” if you’re using base LaTeX[/li][li]in the third of the summation identities, the summand is omitted; it should be x^iy^j[/ul][/li]Other than that it looks right to me, though if you just want particular values of C(n,k) I suspect using the generating function is rather inefficient.
I haven’t found any further simplifications of the single sum I found earlier (though I haven’t asked Mathematica or Maple yet), but here it is if you’re curious:
(some of the later terms in this sum will be zero: the left-hand \choose when m > n-k, and the right-hand \choose when m > k). The terms in this sum are pretty efficient to compute: since 2^{a+1}{a+1 \choose k} = (2(a+1)/(a+1-k)) 2^a{a \choose k}, each one can be computed from the previous one with only three integer multiplications.
The SDMB isn’t the best text editor, especially since a while back it changed so the background of the text field is almost exactly the same gray as the highlight color. Really, I was providing the derivation on the understanding that you and ultrafilter are capable of filling in any errata.
Well, there do exist techniques to (try to) pull out closed forms from generating functions, but I’m not really an expert on that. As for efficiency, I could never push myself to care about runtimes. I’d be interested in a closed form to see, for instance, growth rates of the function.
Not meant as a criticism; it’s a good derivation. But I was going cross-eyed trying to find that extra }; didn’t want to subject ultrafilter to the same eyestrain.
min[sub]k[/sub](C(n, k)) is [symbol]Q/symbol (see the boundary conditions), and max[sub]k[/sub](C(n, k)) seems to be [symbol]Q/symbol, which makes sense given the recurrence relation.