By _Muhammad, history, 13 months ago, ,

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?

• +8

 » 13 months ago, # | ← Rev. 2 →   -21
•  » » 13 months ago, # ^ |   +29 Hahaha, it links back to the this page!
•  » » » 13 months ago, # ^ |   -27 Ok, check this.
•  » » » » 13 months ago, # ^ |   +36 This is so dumb, why is it so hard for you to check your own lmgtfy before posting? It doesn't provide any clear immediate answer and this page is among google search results.
•  » » 13 months ago, # ^ |   0
•  » » 13 months ago, # ^ |   0
 » 13 months ago, # |   0 There exists a formula for Fibonacci series. But actually, it's not O(1). Most of the complex formula include exponents or something else which are in fact O(log N). In case of Fibonacci series, look up Binet's formula.
 » 13 months ago, # |   +1 You may want to look up methods of solving recurrences in some book or on the net. Without going into the details, I'll just tell you that the fibonacci series indeed has a formula involving the golden ratio, it's called Binet's Formula. You may want to look at this page to get started.
•  » » 13 months ago, # ^ |   -13 Binet's formula is an approximation formula. It does not give precise values for large n
•  » » » 13 months ago, # ^ |   +58 No Binet's formula is exact. In programming it's not, as doubles aren't arbitrary precision. But the formula itself is exact.
•  » » » » 13 months ago, # ^ |   +32 It can be done exact in modular arithmetics for modulos that have a square root for 5. Such as in where p = 109 + 9.
•  » » » » » 13 months ago, # ^ |   +8 Yeah... that problem (DZY Loves Fibonacci) was kinda lame imo. Finding quadratic reciprocity isn't that easy of a task itself. There were a lot better solutions that didn't rely on that.
•  » » » » » » 13 months ago, # ^ |   +24 I'd say it's cool, but not a good idea for a problem in a rated contest. It requires much more than the problem itself, such as an already-implemented Tonelli-Shanks template on your personal computer :D
 » 13 months ago, # |   +12 If recurrence is generated by linear composition of previous values, it can be rewritten in matrix form, and then matrix power has closed form granted by Jordan form. But it, of course, involves n-th powers of eigenvalues.
 » 13 months ago, # |   0 If you have f(n)=af(n-1)+bf(n-2)+cf(n-3)+df(n-4)+ef(n-5)+ff(n-6), then to solve for f(n) you need to find roots of f+ex+dx^2+cx^3+bx^4+ax^5=x^6. Then f(n) will be linear combination of these roots to the nth power. But it is really hard to solve nth degree polynomial.
•  » » 13 months ago, # ^ |   0 This is simple consequence of eigenvalues of matrix
•  » » » 13 months ago, # ^ |   0 Yes, but it is not a closed form formula.
•  » » » » 13 months ago, # ^ |   0 It is.
 » 13 months ago, # |   0 Please, provide exact definition of "simple recurrence relation". We can't speak about generic solutions before we make our terms consistent.For linear recurrent relations solution is well known.
 » 13 months ago, # |   -9 Binet's formula Fn=(((1+√5)/2)^n − ((1−√5)/2)^n)/√5
 » 13 months ago, # |   0 I don't know many things about it, but in that case there wouldn't be any DP!!!You could just solve it O(1), am I wrong?? Or maybe that's because it's really hard to get the O(1) formula...
 » 13 months ago, # |   +24 There exist two types of recurrences: ones that have closed forms and ones that don't.For the first type of recurrences, with closed forms, still, one may not be able to calculate the nth term in O(1). Just like Fibonnaci sequence, one need to calculate it in at least time.For the second type, there's no such formula exist, not to mention the complexity.