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