Double summation formula of an arbitrary function

Question

I came up with this formula:

$\sum_{t=1}^N $$\sum_{s=1}^N f(t-s)$= $\sum_{k=-N+1}^{N-1}$$(N-\left\lvert k \right\rvert)$ $ f(k)$

and I wonder how to prove it.

Thank in advance for help

Answer 1

\begin{align*} \sum_{t=1}^N \sum_{s=1}^N f(t-s) &= \sum_{t=1}^N \sum_{k=t-N}^{t-1} f(k) \quad\text{(set $k=t-s$)} \end{align*} Notice that the smallest possible value of $k$ is $1-N$ and the largest is $N-1$. Now fix a value $1-N \leq k_0\leq N-1$. If $t-N \leq k_0 \leq t-1$, then $f(k_0)$ will appear in the sum $\sum_{k=t-N}^{t-1} f(k)$.

For how many values of $t$ does this happen? Rearranging the inequality, we see that such a $t$ must satisfy $k_0+1\leq t \leq k_0+N$. However, we know $t$ must also between $1$ and $N$. If $1-N \leq k_0 \leq 0$, then this implies we must have $1 \leq t \leq k_0+N$, and the number of values of $t$ for which this holds is $k_0+N = -|k_0|+N$. On the other hand, if $0 \leq k_0 \leq N-1$, then we must have $k_0+1 \leq t\leq N$, and the number of values of $t$ for which this holds is $N-(k_0+1)+1 = N-k_0=N-|k_0|$.

In any case, for all values of $k_0$ between $1-N$ and $N-1$, the term $f(k_0)$ will appear in the sum $(N-|k_0|)$ times. Therefore the sum is equal to $$\sum_{k=1-N}^{N-1} (N-|k|)f(k).$$

Answer 2

$$\sum_{t=1}^N \sum_{s=1}^N f(t-s) = \sum_{t=1}^N \sum_{k=t-N}^{t-1} f(k) = \sum_{t=1}^N \sum_{k=1-N}^{N-1} f(k) \mathbf{1}_{1 \le t-k \le N} = \sum_{k=1-N}^{N-1} f(k) \sum_{t=1}^N \mathbf{1}_{1 \le t-k \le N} = \sum_{k=1-N}^{N-1} (N-|k|) f(k)$$ where in the last step $N-|k|$ is the number of integers $t$ satisfying both $1 \le t \le N$ and $1+k \le t \le N+k$ fora fixed $k \in \{-(N+1), \ldots, N+1\}$.