Find recurrence relation for a sum

Question

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.

Answer 1

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) *)

Answer 2

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.