3
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – drxy Jan 26 '16 at 22:10
  • $\begingroup$ @drxy My revision should work better, at least for moderate n. $\endgroup$ – bbgodfrey Jan 26 '16 at 23:05
  • $\begingroup$ @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. $\endgroup$ – Mr.Wizard Jan 27 '16 at 0:29
  • $\begingroup$ @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. $\endgroup$ – bbgodfrey Jan 27 '16 at 0:49
  • $\begingroup$ I meant to say my timings where for f[150] but I somehow forgot that. You're welcome, and thank you. $\endgroup$ – Mr.Wizard Jan 27 '16 at 0:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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