# Is there a way to write this recurrence relation in faster-to-program manner?

I have the following recurrence relation for some coefficients

$$b_{n+2} = \frac{1}{(n+3)(n+2)P_0} \sum_{k=1}^n (n-k+2) (n-k+1) b_k b_{n-k+2}, \quad n>1$$

with $b_1$ to $b_3$ and $P_0$ being the initial conditions of the series.

The problem is that I have to calculate the series to a high value of $n$ (about 10000, or sometimes even more). And since the $n$th term depends on a sum that involves all the other terms before it, the calculation is really slow. So I'm trying to simplify it in some way to make it faster to program. (Getting rid of the sum would be already a good start for example.)

The best cases scenario would be to have $b_n = F(n)$, which of course would be simpler to read and way faster to program, but I'm not sure this is possible. Is there a way to re-write the relation in a way that's faster to calculate? (Or at the very least in a simpler way?)

If you prove that it isn't possible to achieve what I want I'd be also extremely grateful. That way I can stop worrying about it.

Thank you.

• You have any specific meaningful values of $b_0,...,b_3$? Then you could search in OEIS. – san Apr 21 '16 at 3:21
• The values aren't fixed, if that's what you mean. They depend on the boundary values of a problem. They're also not integers. Nice reference, though (OEIS). I hadn't heard of it. – TomCho Apr 22 '16 at 19:26
• Another thought: Why you need $b_0$? It doesn't appear in the sum. – san Apr 22 '16 at 20:13
• I take it that you are attempting series solution of $$P_0(xy^{\prime\prime}+2y^{\prime})=xyy^{\prime\prime}$$ or sometihng like that? – user5713492 Apr 24 '16 at 19:25
• Just some random observations. The constants will be triangular numbers (arithmetic sums) which have linear differences (both in k and n). Apart from that you can note that this is a convolution equation. It's like saying that a time shifted version of a function is equal to a convolution of the function with itself. Time shifting and convolution are fast to make in the fourier domain. Maybe you can make an linear solver update-scheme with costs in both ordinary domain and the fourier domain. – mathreadler May 2 '16 at 23:12