# Find recurrence relation for a sum

Let's say I want to find a recursive equation for an exponentially weighted moving average

EV[t_]:=(a-1)/(a^t-1)*Sum[a^(t-i)*x[i],{i,1,t}]


I can do that manually to come up with an equation

EVR[t_]:=(a-1)/(a^t-1)*x[t]+(a^t-a)/(a^t-1)*EVR[t-1]
EVR[1]=x[1]


We can check whether the manually derived equation is correct via

Table[(EV[i]==EVR[i])//FullSimplify,{i,2,10}]


which gives

{True,True,True,True,True,True,True,True,True}


In Mathematica, how would I find the recursive equation for EVR[t] assuming that the equation for EV[t] is given?

Also, the exponentially weighted moving average is just a minimal example. The actual sums are more complicated.

• EVR is not recursive at all. It refers to EV and not to itself. – Sjoerd C. de Vries Apr 29 '15 at 15:26
• I have defined EVR so that the check in the next line is shorter. Otherwise, I would have had to write Table[(EV[t]==(a-1)/(a^t-1)*x[t]+(a^t-a)/(a^t-1)*EV[t-1])//FullSimplify,{t,2,10}]. But I will change this to make it clearer. – cryo111 Apr 29 '15 at 15:30
• Perhaps I'm mistaken, but I feel you missed the point. In a recurrence equation you relate a given element of a sequence to one or more earlier or later elements of the same sequence. In this case, your second definition then should have EV[t_] as the left-hand side, which would be problematic as you haven't specified a stopping criterion. – Sjoerd C. de Vries Apr 29 '15 at 15:33
• Anyway, most folks want to go the other way: they have a recursive function and need to have a closed form solution. That can be done with RSolve. Not sure if it is possible to go the other way. – Sjoerd C. de Vries Apr 29 '15 at 15:42
• I made some changes to my post to make it clearer. – cryo111 Apr 29 '15 at 15:46

Here is a possible approach. Would need some work to generalize to higher degree though.

recursiveSum[fac_.*Sum[term_*x_[i_], {i_, n_}]] :=
Module[
{topterm, c, genterm, soln},
topterm = fac*term*x[i] /. i -> n;
genterm = Table[fac*term /. n -> nn, {nn, n - 1, n}];
soln = c /. First[Solve[{c, 1}.genterm == 0, c]];
topterm + Together[soln]*Sum[term*x[i], {i, n - 1}]
]


That example:

recursiveSum[(a - 1)/(a^t - 1)*Sum[a^(t - i)*x[i], {i, t}]]

(* Out[92]= -(((-a + a^t)*Sum[a^(-i + t)*x[i], {i, -1 + t}])/(-1 +
a^t)) + ((-1 + a)*x[t])/(-1 + a^t) *)


I have not found a general solution but one that does hint at it. Based on this post

I have tried the following for t=5:

ElEq = Eliminate[{A == EV[5], EV[4]==B}, Table[x[i],{i, 1, 4}]]
Flatten[Collect[Solve[ElEq,A], {B,x[5]}]]


This gives

{A->(B (a+a^2+a^3+a^4))/(1+a+a^2+a^3+a^4)+x[5]/(1+a+a^2+a^3+a^4)}


Now one can see that the factor for B goes like

Sum[a^i,{i,1,t-1}]/Sum[a^i,{i,0,t-1}]


This can be simplified with FullSimplify to give

(a^t-a)/(a^t-1)


which is the correct factor for EVR[t-1]. The same can be done for x[t], which also gives the correct factor

1/Sum[a^i,{i,0,t-1}]


or simplified

(a-1)/(a^t-1)


An alternative solution:

CoefficientRules[Flatten[Solve[ElEq, A][[1,2]], {B, x[5]}]//FullSimplify


This gives

{{1,0}->1-1/(1+a+a^2+a^3+a^4),
{0,1}->1/(1+a+a^2+a^3+a^4)}


From there it would nice if one could use FindSequenceFunction on the factors for B and x[5] but the expressions seem to be to complicated.

• I do not accept my post as an answer yet because I would rather like to see a general solution. So if anyone has a general solution, I am happy to accept it. – cryo111 Apr 29 '15 at 16:38