# Correct way to use memoization for recurrence relation having an Integral

I am trying to construct a way to make a function for the following recurrence relation. $$Q(N,L) = \int_{0}^{L-(N-1)a} Q(N-1, L-a-z) dz$$, with the initial condition $Q(2,L) = \frac{1}{2} (a-L)^2$ for positive real numbers $a$ and $L$.

Since it involves recurrence relation, I tried to use a basic memoization trick below.

Q[n_, L_] := Q[n, L] =
Integrate[  Q[n - 1, L - a - z] , { z, 0, L - (n - 1) a}]

Q[2, L_] = 1/2 (a - L)^2


However, I found that this is not correct approach since the memoized $Q(k, L)$'s are not functions $L$ but some specific values like $Q(k, L - a-z)$. Even worse, this approach does not yield correct results. For example, I got $Q(4,L) = \frac{1}{12} (L-3 a)^4$ instead of correct value $Q(4,L) = \frac{1}{24} (L-3 a)^4$.

What is the correct way to achieve the desired behavior?

EDIT: As pointed out in the comment, this expression even does not yield a correct solution without the memoization parts. Therefore the question should be "What is the correct expression for the equation?". I would be more interested if the solution is somehow memoized.

• Even without memoization, I get the 1/12-answer, so memoization is not the issue, it seems. – Per Alexandersson Oct 3 '14 at 21:55
• @PerAlexandersson That is right. So strictly speaking, my question would be "What is the correct mathematica way to get a solution of this equation. However, it would be even better if this solution supports memoization. – Sungmin Oct 3 '14 at 22:01
• Pardon me if it should be obvious: can you demonstrate that 1/24 ... is the correct value? – Mr.Wizard Oct 3 '14 at 22:13
• @Mr.Wizard According to my manual calculation I got the value. I guess belisarius's answer already verifies my result. – Sungmin Oct 3 '14 at 22:22

## 2 Answers

Q[n_, L_] :=  Q[n, L] = Integrate[Q[n - 1, L] /. L :> L - a - z, {z, 0, L - (n - 1) a}]

Q[2, L_] = 1/2 (a - L)^2

Q[4, L]

(* 1/24 (-3 a + L)^4 *)

• Simple and elegant. Thank you. – Sungmin Oct 3 '14 at 22:27
• Is there an explanation why OP:s code does not work, and this does? – Per Alexandersson Oct 4 '14 at 8:36
f[n_] := First@
Nest[{Integrate[#[[1]] /. L :> L - a - z, {z, 0,
L - #[[2]] a}], #[[2]] + 1} &, {1/2 (a - L)^2, 2}, n - 2]


Test: (f(2) to f(10)):

Table[f[j], {j, 2, 10}]


yields

{1/2 (a - L)^2, -(1/6) (2 a - L)^3, 1/24 (-3 a + L)^4, -(1/120) (4 a - L)^5,
1/720 (-5 a + L)^6, -((6 a - L)^7/5040), (-7 a + L)^8/40320,
-((8 a - L)^9/362880), (-9 a + L)^10/3628800}