_Muhammad's blog

By _Muhammad, history, 9 months 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

»
9 months ago, # |
Rev. 2   Vote: I like it -21 Vote: I do not like it
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
9 months 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.

  • »
    »
    9 months 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

    • »
      »
      »
      9 months 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.

      • »
        »
        »
        »
        9 months 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.

        • »
          »
          »
          »
          »
          9 months 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.

          • »
            »
            »
            »
            »
            »
            9 months 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

»
9 months 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.

»
9 months 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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is simple consequence of eigenvalues of matrix

»
9 months 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.

»
9 months 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

»
9 months 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...

»
9 months 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.