# 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, 2015 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. Apr 3, 2015 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, 2015 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, 2015 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, 2015 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. Apr 3, 2015 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, 2015 at 9:09
• That would be my interpretation. Of course, there may well be no closed form solutions. Apr 3, 2015 at 13:12