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

Правка en1, от _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?

Теги recurrence relation, formula, conversion


  Rev. Язык Кто Когда Δ Комментарий
en1 Английский _Muhammad 2019-01-01 16:40:24 845 Initial revision (published)