Factorial property of a double summation

Question

I just proved the following identity, simply by expanding the sums:

$$ \sum_{j=1}^h \sum_{i=0}^{j-1} f^i x_{j-i} = \sum_{j=1}^h \sum_{i=0}^{j-1} f^i x_{h-j+1} $$

I was wondering... is there a property of summation, a trick on the indices, or anything that allows one to directly write this identity without checking it by hand?

When you do it by hand, the trick is to factor terms.

Answer 1

You can do it with standard manipulations involving reversing the order of summation and playing with the indices:

$$\begin{align*} \sum_{j=1}^h\sum_{i=0}^{j-1}f^kx_{j-i}&=\sum_{i=0}^{h-1}\sum_{j=i+1}^hf^ix_{j-i}\\ &=\sum_{i=0}^{h-1}f^i\sum_{k=1}^{h-i}x_k&(k=j-i)\\ &=\sum_{i=0}^{h-1}f^i\sum_{\ell=i+1}^hx_{h+1-\ell}&(\ell=h+1-k)\\ &=\sum_{i=0}^{h-1}f^i\sum_{j=i+1}^hx_{h-j+1}&(j=\ell)\\ &=\sum_{i=0}^{h-1}\sum_{j=i+1}^hf^ix_{h-j+1}\\ &=\sum_{j=1}^h\sum_{i=0}^{j-1}f^ix_{h-j+1}\;. \end{align*}$$

Note, though, that this is really just a fully computational version of Gerry Myerson’s argument, which for many readers will be easier to follow.

Answer 2

Let's find the coefficient of $f^i$ on both sides. On the left, the terms with $j\le i$ contribute nothing, so it's $\sum_{j=i+1}^hx_{j-i}$, which is $x_1+x_2+\cdots+x_{h-i}$. Same is true on the right, so it's $\sum_{j=i+1}^hx_{h-j+1}$, which is $x_{h-i}+\cdots+x_1$. These are equal.