0
$\begingroup$

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.

  • 0
    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}$.2011-11-12
  • 0
    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.2011-11-12
  • 2
    @Michael: Why would you want to eat silverware when mashed potatoes are available?2011-11-12
  • 0
    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?2011-11-12
  • 0
    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.2011-11-12

1 Answers 1

1

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.

Another solution:

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} $$