Jump to content

  • Log In with Google      Sign In   
  • Create Account

#ActualÁlvaro

Posted 21 January 2013 - 08:55 AM

This doesn't answer the original question, but this is how I like to think of sequences like this one.

Take the matrix
    0 1 0 0
M = 0 0 1 0
    0 0 0 1
    4 3 2 1

and the vector
    f(n-4)
v = f(n-3)
    f(n-2)
    f(n-1)

When you multiply M*v you get the vector
    f(n-3)
    f(n-2)
    f(n-1)
    f(n)

So the indices are pushed by one in this operation. If you want to advance two steps at once, use M^2.

Now, in order to compute f(n), compute M^n, and multiply the result by the first four terms (0 1 2 3). Computing a power of a matrix can be done in O(log(n)) multiplications. You can also make this computation more efficient by realizing that the matrices involved all live in a 4-dimensional linear subspace, and you can define a special type that contains 4 numbers with the appropriate operations (this part is a bit tricky).

This method is not only computationally efficient, but it gives you a much deeper understanding of the situation. For instance, if you want to find an explicit formula for f(n), you just need to diagonalize M.

#1Álvaro

Posted 21 January 2013 - 08:51 AM

This doesn't answer the original question, but this is how I like to think of sequences like this one.

Take the matrix
    0 1 0 0
M = 0 0 1 0
    0 0 0 1
    4 3 2 1

and the vector
    f(n-4)
v = f(n-3)
    f(n-2)
    f(n-1)

When you multiply M*v you get the vector
    f(n-3)
    f(n-2)
    f(n-1)
    f(n)

So the indices are pushed by one in this operation. If you want to advance two steps at once, use M^2.

Now, in order to compute f(n), compute M^n, and multiply the result by the first four terms (0 1 2 3).

This method is not only computationally efficient, but it gives you a much deeper understanding of the situation. For instance, if you want to find an explicit formula for f(n), you just need to diagonalize M.

PARTNERS