# Calculating $f(x)$ using matrix exponentiation

Having polynomial in form $\sum \limits_{i=1}^{n} c_i x^i$ and linear recurrence, for example $$R(n)=2 R(n-1)+3R(n-2) + f(n)$$

where $f(n)$ is our polynomial and $R(n)$ is linear reccurence, how can we calculate $R(n)$?

So in other words having $f(n-1)$ how can we calculate $f(n)$?

I'm a bit confused and can't get proper states for my matrix.

Thanks for any hints.

-
I am not sure I fully understand what you are trying to do. But let $f(x)=\sum_{i=0}^m c_ix^i$. (Note the upper index!) You need to calculate $f(n+1)$ from $f(n)$ as part of the matrix multiplication. If you use as additional "states" the current $n^1, n^2, \dots, n^m$, then calculating the values at $n+1$ is a mess. It is easier to first express $f(x)$ as $\sum d_i \binom{x}{i}$. If we have the $\binom{n}{i}$ as states, they are easy to update "linearly" since $\binom{n+1}{i}=\binom{n}{i}+\binom{n}{i-1}$. – André Nicolas Nov 12 '11 at 1:51
Using an asterisk for ordinary multiplication in TeX is like eating mashed potatoes with your hands when silverware is available. The asterisk began to be used for that purpose in computer programming languages that could only use characters that are on standard keyboards. In TeX one can write $3\times 5$ or $3\cdot5$ or $3pq$, etc. I edited the question accordingly. – Michael Hardy Nov 12 '11 at 3:28
@Michael: Why would you want to eat silverware when mashed potatoes are available? – joriki Nov 12 '11 at 9:37
Maybe you've heard about how linear recurrences can be recast as the evaluation of matrix powers, and you've forgotten quite a few details? – J. M. Nov 12 '11 at 10:54
Even having answered my interpretation of your question, I am still confused when I read your question. You ask both "how can we calculate $R(n)$?" and "how can we calculate $f(n)$?" Since computing $f(n)$ given $R(n)$ is trivial, I assume that you really want to compute $R(n)$ given $f(n)$. Perhaps you could refine the question a bit. – robjohn Nov 12 '11 at 18:19

I assume that you mean $$f(x)=\sum_{i=0}^nc_ix^i$$ In that case, we are looking at $$f(x)=R(x)-2R(x-1)-3R(x-2)=(I+S)(I-3S)R(x)\tag{1}$$ where $S$ is the shift operator $Sf(x)=f(x-1)$. Since the general solution of $$R_0(n)-2R_0(n-1)-3R_0(n-2)=0\tag{2}$$ is $R_0(n)=a_{-1}(-1)^n+a_33^n$, any solution of $(1)$ is unique modulo solutions of $(2)$.
One way to get a particular solution of $(2)$, create the matrix $M\in\mathbb{R}^{(n{+}1)\times(n{+}1)}$ satisfying $$M\begin{bmatrix}1\\x\\x^2\\\vdots\\x^n\end{bmatrix}=\begin{bmatrix}(I+S)(I-3S)1\\(I+S)(I-3S)x\\(I+S)(I-3S)x^2\\\vdots\\(I+S)(I-3S)x^n\end{bmatrix}\tag{3}$$ Then, a particular solution of $(1)$ would be $$\begin{bmatrix}c_0&c_1&c_2&\cdots&c_n\end{bmatrix}M^{-1}\begin{bmatrix}1\\x\\x^2\\\vdots\\x^n\end{bmatrix}\tag{4}$$ $M$ is lower triangular with $-4$s on the diagonal, therefore, invertible.
We can also derive a particular polynomial solution by noticing that Taylor's Theorem implies that, for polynomials at least, $$Sf(x)=e^{-D}f(x)\tag{5}$$ where $D=\frac{\mathrm{d}}{\mathrm{d}x}$. $(5)$ is one of the motivations behind the Euler-Maclaurin Sum Formula.
Using $(5)$, $(1)$ becomes $$f(x)=(I-2e^{-D}-3e^{-2D})R(x)\tag{6}$$ Noting that $$(1-2e^{-x}-3e^{-2x})^{-1}=-\tfrac{1}{4}-\tfrac{1}{2}x-\tfrac{9}{16}x^2-\tfrac{25}{48}x^3-\tfrac{15}{32}x^4-\dots\tag{7}$$ we can get a partcular solution of $(1)$ with \begin{align} R(x) &=(1-2e^{-D}-3e^{-2D})^{-1}f(x)\\ &=(-\tfrac{1}{4}I-\tfrac{1}{2}D-\tfrac{9}{16}D^2-\tfrac{25}{48}D^3-\tfrac{15}{32}D^4-\dots)f(x)\tag{8} \end{align}