just like you do with f terms , you just have to increase a column and a row in the transformation matrix to accomodate any polynomial
(As far as i know)
for eg.
for f(i) = af(i-1) +bf(i-3)
you must have made
|0 1 0 |
|0 0 1 |
|b 0 a |
for f(i)=f(i-1)+3f(i-3)+2*i
you can make
|0 1 0 0 0|
|0 0 1 0 0|
|b 0 a 2 0|
|0 0 0 1 1|
|0 0 0 0 1|
Let this transformation matrix be T
and
we multiply it by
| f(i-3) |
| f(i-2) |
| f(i-1) |
| i |
| 1 |
to get
| f(i-2) |
| f(i-1) |
| f(i) |
| i+1 |
| 1 |
and the recurrence continues.
Feel free to do your research though