Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Can every recurrence relation be converted to a O(1) formula?

Revision en1, by _Muhammad, 2019-01-01 16:40:24

I can convert some simple recurrence relation to a mathematical formula.

Example: F(n) = n + F(n-1), if n > 0 and F(0) = 0; This recurrence relation can be converted into the formula: F(n) = (n*(n+1))/2

But for many other recurrence relations I am unable to do so.
Example: Lets consider the fibonacci sequence. F(n) = F(n-1) + F(n-2), if n > 1 and F(0) = 0, F(1) = 1; I tried hard to convert this recurrence relation to a formula, but failed.

So, my question is it actually possible to convert every recurrence relation to a O(1) formula? If not, then how do I determine that the recurrence relation does not have an implicit formula? If yes, then is there any rule of thumb for converting? #### History

Revisions Rev. Lang. By When Δ Comment
en1 _Muhammad 2019-01-01 16:40:24 845 Initial revision (published)