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.

  • $\begingroup$ You have any specific meaningful values of $b_0,...,b_3$? Then you could search in OEIS. $\endgroup$
    – san
    Apr 21, 2016 at 3:21
  • $\begingroup$ 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. $\endgroup$
    – TomCho
    Apr 22, 2016 at 19:26
  • $\begingroup$ Another thought: Why you need $b_0$? It doesn't appear in the sum. $\endgroup$
    – san
    Apr 22, 2016 at 20:13
  • 2
    $\begingroup$ I take it that you are attempting series solution of $$P_0(xy^{\prime\prime}+2y^{\prime})=xyy^{\prime\prime}$$ or sometihng like that? $\endgroup$ Apr 24, 2016 at 19:25
  • 2
    $\begingroup$ 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. $\endgroup$ May 2, 2016 at 23:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.