# How can I find the coefficients of the next recursive symbolic function?

I have the following function $$f(x+3k) = -mf(x+2k)+f(x)$$. If we get $x=x+k$, then $$f(x+4k) = -mf(x+3k)+f(x+k) = m^2f(x+2k)+f(x+k)-mf(x)$$. Also we obtain the coefficients of the final functions, $\{ f(x+2k),f(x+k),f(x)\}$, as $\{m^2,1,-m\}$. How can I find for the coefficients of the functions, $\{ f(x+2k),f(x+k),f(x) \}$, for the cases $\{x=x+2k, x=x+3k, \ldots \}$ by using Mathematica.

The recurrence relation can be represented by

f[0] = f0; f[1] = f1; f[2] = f2; f[n_] := f[n] = Simplify[-m f[n - 1] + f[n - 3]]


based on which, the coefficients of {f2, f1, f0} for n = 4 are given by

CoefficientArrays[f[4], {f2, f1, f0}][[2]] // Normal
(* {m^2, 1, -m} *)


which agrees with the results predicted in the question. Coefficients for larger values of n are obtained similarly. For instance

CoefficientArrays[f[5], {f2, f1, f0}][[2]] // Normal
(* {1 - m^3, -m, m^2} *)

CoefficientArrays[f[25], {f2, f1, f0}][[2]] // Normal
(* {36 m^2 - 462 m^5 + 1287 m^8 - 1365 m^11 + 680 m^14 - 171 m^17 + 21 m^20 - m^23,
1 - 84 m^3 + 462 m^6 - 715 m^9 + 455 m^12 - 136 m^15 + 19 m^18 - m^21,
-8 m + 210 m^4 - 792 m^7 + 1001 m^10 - 560 m^13 + 153 m^16 - 20 m^19 + m^22} *)


Improved Timing

In a comment below, Mr. Wizard suggested using Factor instead of Simplify in the definition of f[n]. This modification reduces AbsoluteTiming from 4.2 sec to 0.12 sec for f[100]. Note that not using either make the computation prohibitively slow and memory-intensive.

• Thank you @bbgodfrey. I think your code would be slow for higher order indexes. How can I find the (?) coefficients in the equation $f(x+5k)=-mf(x+4k)+f(x+2k)=?f(x+2k)+ ?f(x+k) + ?f(x)$.
– drxy
Jan 26, 2016 at 22:10
• @drxy My revision should work better, at least for moderate n. Jan 26, 2016 at 23:05
• @drxy and bbgodfrey, I think you will find that Factor is a better choice than Simplify here; on my system (v10.1) the function with Simplify takes 9.8 seconds, whereas after substituting Factor it takes only 0.187 second. The expression is fractionally longer but I don't think it will matter for your application. Jan 27, 2016 at 0:29
• @Mr.Wizard Right, you are. f[100] takes about 4 sec with Simplify and only 3% of that with Factor. I shall modify my answer, citing your contribution. Thanks. Jan 27, 2016 at 0:49
• I meant to say my timings were for f[150] but I somehow forgot that. You're welcome, and thank you. Jan 27, 2016 at 0:54

A slick reformulation of bbgodfrey's answer is to recognize that the required computation is equivalent to evaluating an appropriate matrix power:

With[{n = 5},
MatrixPower[{{-m, 1, 0}, {0, 0, 1}, {1, 0, 0}}, n - 2, {1, 0, 0}]] // Simplify
{1 - m^3, -m, m^2}

With[{n = 25},
MatrixPower[{{-m, 1, 0}, {0, 0, 1}, {1, 0, 0}}, n - 2, {1, 0, 0}]] // Simplify
{-m^2 (-36 + 462 m^3 - 1287 m^6 + 1365 m^9 - 680 m^12 + 171 m^15 - 21 m^18 + m^21),
1 - 84 m^3 + 462 m^6 - 715 m^9 + 455 m^12 - 136 m^15 + 19 m^18 - m^21,
m (-8 + 210 m^3 - 792 m^6 + 1001 m^9 - 560 m^12 + 153 m^15 - 20 m^18 + m^21)}


Note that I have explicitly used the action form of MatrixPower[], since we are only interested in a single column, and not the whole matrix.