0

Matrix Exponentiation can be used to solve Linear Recurrence . I know how to solve linear recurrences like :

$f(n) = f(n-k_1) + f(n-k_2) + ... +\ constant$

But i couldn't find any information on how to solve recurrences like

$f(n) = f(n-k_1) + f(n-k_2) + ... + n^m$

or

$f(n) = f(n-k_1) + f(n-k_2) + ... + n\cdot m$

or

$f(n) = f(n-k_1) + f(n-k_2) + ... + k^n$

i.e.

involving an '$n$' term.

Can anyone provide me with any link or explain how to solve such recurrences or how to form the initial matrix whose power will be used to solve the recurrence?

This is required in :

http://www.spoj.com/problems/ASUMHARD/

iadvd
  • 8,875
bytes1337
  • 1
  • 1

1 Answers1

1

For $k^n$ just place $k$ in the first free diagonal element where all other on the same row are 0, you will find $k^n$ in that position in the exponentiated matrix:

$${\bf A} = \left(\begin{array}{cc}k&{\bf 0}^T \\ * & * \end{array}\right) \Rightarrow {\bf A}^n = \left(\begin{array}{cc}k^n&{\bf 0}^T \\ * & * \end{array}\right)$$

To get $mn$ and $n^m$ you can check my answer to this question.

In terms of recurrences which may be easier for you since you have already dealt with them this means to use the fact that $n+1 = 1+(n)$ (simplest possible recurrence), $(n+1)^2 = n^2 + 2n + 1$ et.c. I.e. binomial expansions of monomials.

Community
  • 1
mathreadler
  • 25,824