3
$\begingroup$

I would like to know if there exists a closed form formula to the following recurrence:

  • $f(s, 0) = 1$
  • $f(s,b) = \displaystyle\sum_{i=1}^{min(s, b)} \left[ (s-i+1)\times f(i, b-i) \right] $

This recurrence gives the solution to problem F of the ICPC Latin American regionals of 2019.

The problem itself can be solved in $O(n^2)$ by using dynamic programming and keeping a matrix of precomputed sums. I'm just curious about if there is some technique that allows obtaining a closed formula to recurrences like this, so I can solve it in better runtime complexity.

$\endgroup$
1
$\begingroup$

I do not have a strong mathematical background, but I am afraid that recursive functions cannot always been written in closed form.

ex1.

f(n) = sum([1,2,..,n]) can be written as
f(1) = 1
f(n) = n + f(n-1)

Of course f(n) = n*(n+1)/2

ex2.

f(n) = prod([1,2,3,4,..n]) = n!
f(1) = 1
f(n) = n * f(n-1)

No known closed formula :( (I don't even know how to prove something like this)

In your case, I find it extremely difficult because your recursion makes use of an if statement under the min() function.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.