Search code examples
mathrecurrence

How to solve a general recurrence?

Is there a way to solve a general recurrence relation of the form

a(n)=a(n-1) * a(n-2)....

I mean I can use the matrix method to solve a relation of the form

F(n)=a1*F(n-1) + a2*F(n-2).......+ ak*F(n-k)

but what to do when there is a '*' sign instead of '+'

Solution

  • Use logarithms:

    a(n) = a(n-1) * a(n-2) * a(n-3) * ....

    Take log of both sides:

    log(a(n)) = log(a(n-1) * a(n-2) * a(n-3) * ...)

    Use the fact that log(a * b) = log(a) + log(b) to split up the factors:

    log(a(n)) = log(a(n-1)) + log(a(n-2)) + log(a(n-3)) + ...

    Now, if you just say that F(n) = log(a(n)) then this equation looks just like your second equation. Use the matrix method to solve for log(a(n)):

    log(a(n)) = X

    Which leaves:

    a(n) = e ^ X

    (Assuming you take natural logarithms)