I have my recurrence relation as f(n) = a*f(n-1) + b*f(n-2) + n*n how to solve that relation using matrix exponential

I have tried like

| f(n)   |   | a b 1 | ^ (n-1)       |  f(1) |
| f(n-1) | = | 1 0 0 |           *   |  f(0) |
| f(n-2) |   | 1 0 0 |               |  n*n  |

but it fails due to base matrix contains n*n in the last row how could I solve this using matrix exponential.


closed as unclear what you're asking by Namaste, Mostafa Ayaz, Shailesh, Brian Borchers, user223391 Jul 29 '18 at 22:01

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I see no reason for matrix exponential to intervene here unless your instructor has said that there is a solution with this tool... $\endgroup$ – Jean Marie Jul 27 '18 at 15:44

You are thinking that when you have a recurrence $f_n = af_{n-1}+bf_{n-2}$, then it defines a matrix recurrence $\def\f{{\bf f}}\f_n=A\f_{n-1}$ whose solution is $\f_n=A^{n-1}\f_1$. Here, $$\f_n=\begin{bmatrix}f_n\\f_{n-1}\end{bmatrix},\qquad A=\begin{bmatrix}a & b\\1 & 0\end{bmatrix}$$ Unfortunately, things do not work out so cleanly in your problem. Let $ \def\b{{\bf b}}\b = \begin{bmatrix}1\\0\end{bmatrix}, $ the recurrence is now $$ \f_n = A\f_{n-1} +n^2\b $$ Instead, the solution is now $$ \f_n = A^{n-1}\f_1 + A^{n-2}\b 2^2 + A^{n-3}\b 3^2 + \dots + A\b({n-1})^2 +\b n^2 $$ Noting that $A$ is invertible, we can write this as $$ \f_n = A^{n-1}\f_1 + A^{n}\left(\sum_{k=2}^n k^2A^{-k}\right)\b $$ There does exist a closed form for $\sum_{k=2}^n k^2A^{-k}$, but it is messy. In general, the closed form for $$ \sum_{k=2}^n k^2x^k $$ can be bound by starting with the equation $x^2 + x^3 + \dots + x^n=\frac{x^2-x^{n+1}}{1-x}$, the differentiating both sides, then multiplying by $x$, then differentiating again, then multiplying by $x$ again. You can then substitute $x=A^{-1}$ into the resulting formula.

However, I think this method will only work when $A$ does not have $1$ as an eigenvalue. More subtle methods would be required in the case.

There is a different way to approach the problem. Take the four equations $$ \begin{align} f_n &= af_{n-1} + bf_{n-2} + n^2\tag{a}\\ f_{n-1} &= af_{n-2} + bf_{n-3} + (n-1)^2\tag{b}\\ f_{n-2} &= af_{n-3} + bf_{n-4} + (n-2)^2\tag{c}\\ f_{n-3} &= af_{n-4} + bf_{n-5} + (n-3)^2\tag{d}\\ \end{align} $$ and consider the equation $(a)-3(b)+3(c)-(d)$. You will find that this new equation is a recurrence for $f_n$ in terms of $f_{n-1},f_{n-2},\dots,f_{n-5}$, where there is no longer an $n^2$. You can then solve this new recurrence with a matrix exponential.


Not the answer you're looking for? Browse other questions tagged or ask your own question.