_Muhammad's blog

Can every recurrence relation be converted to a O(1) formula?
By _Muhammad, history, 6 years ago, In English

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?

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it -21 Vote: I do not like it

Click

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Binet's formula is an approximation formula. It does not give precise values for large n

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +58 Vote: I do not like it

      No Binet's formula is exact. In programming it's not, as doubles aren't arbitrary precision. But the formula itself is exact.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +32 Vote: I do not like it

        It can be done exact in modular arithmetics for modulos that have a square root for 5. Such as in where p = 109 + 9.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +24 Vote: I do not like it

            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

            → Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is simple consequence of eigenvalues of matrix

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Binet's formula Fn=(((1+√5)/2)^n − ((1−√5)/2)^n)/√5

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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...

→ Reply
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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.

→ Reply