# How to solve for the closed form of this recurrence?

For integers $L,k \geq 0$:

$$T(L,k) = \begin{cases} 0 & \text{if }k \geq d, \text{ever}\\ -a_{k} & \text{if }L=0 \text{ and } k<d\\ a_dT(L-1,k+1) - a_{k}T(L-1,0)& \text{if } L>0 \text{ and } k<d\\ \end{cases}$$

The $a_i$ numbers are all constants (from $a_0$, $a_1$, ..., $a_{d}$), so these terms are static and known.

I am having difficulty trying to parse this into something that is closed form (probably a combinatoric). Is this something Mathematica can do? I've tried RSolve but I don't think I was able to get the syntax right. I'm not even sure if this is possible in Mathematica.

• I think you need to do this by hand for L = 0, then L = 1, etc., until you get enough of a feel for the problem that you can program it. – djp Apr 3 '15 at 0:02
• Welcome to Mathematica.SE! I suggest that: 1) You take the introductory Tour now! 2) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! 3) As you receive help, try to give it too, by answering questions in your area of expertise. – bbgodfrey Apr 3 '15 at 0:03
• @djp I already tried that but was unable to get any of the syntax to work because I have a mix of different things at once. Piecewise conditionals, subscripted variables, etc. – AJJ Apr 3 '15 at 0:05
• Aruka I think that is your problem --- this isn't a problem of "how to program this in Mathematica" so much as "what is the problem in the first place". – djp Apr 3 '15 at 0:42
• @djp I know what the problem is fine. I don't know how to set up the syntax for it in Mathematica, though. – AJJ Apr 3 '15 at 0:48

A straightforward implementation

T[{L_, k_}, d_, coeff_] /; k >= d := 0;
T[{0, k_}, d_, coeff_] := -coeff[[k + 1]];
T[{L_, k_}, d_, coeff_] /; L > 0 :=
T[{L, k}, d, coeff] =
coeff[[d + 1]] T[{L - 1, k + 1}, d, coeff] - coeff[[k + 1]] T[{L - 1, 0}, d, coeff]


Owing to constants (from $a_0$, $a_1$, ..., $a_{d})$, so the $a_k$ should be written as -coeff[[k + 1]], here coeff is $(a_0$, $a_1$, ..., $a_{d})$

Test

T[{2, 2}, 3, {a0, a1, a2, a3}]


$-a2 (a0^2 - a1 a3)$

T[{4, 2}, 3, {3, 5, 6, 4}]

-411

• Very nice answer, but not closed form. – bbgodfrey Apr 3 '15 at 8:13
• @bbgodfrey, thks, I would like to know whether the closed form means that $T[L,k]$ owns a analytical expresstion. – xyz Apr 3 '15 at 9:09
• That would be my interpretation. Of course, there may well be no closed form solutions. – bbgodfrey Apr 3 '15 at 13:12