@dharr Very interesting, it even works for equ0 := u(1) = x[1] instead of equ0 := u(0) = 0, for when the u(0) should be left "undefined". I think the reason this works, it because u(n) is no longer defined recursively on itself (the sum is defined recursively, but the mean is calculated straight from the sum instead of calculated from the previous mean). Thanks! 

@acer This is very much appreciated, I will play around with this some more, thanks!

@Carl Love Thank you for these pointers!

@vv Beautiful, it works like a charm, thank you very much!

Out of curiosity, might you know of any literature (or keywords) that dives deeper into why it helps to rewrite it like that or possibly generalizes this approach to other recurrence relations?

p.s. the images in my post are not super clear, this is the direct command I enter into the Maple document:

rsolve({u(1) = x[1], u(n + 1) = u(n) + (x[n + 1] - u(n))/(n + 1)}, u(n))