finite sum over diagonals

41 Views Asked by At

i am trying to change variables when summing $$\sum\limits_{i=1}^n \sum\limits_{j=1}^n f(i-j)$$ i want to sum over $a=i+j$ and $b=i-j$

i started by drawing a square n by n with dots representing each element in the sum

then i started by considering the lines of constant $b$, over those $a$ goes from $2$ to $2n$ however when $a=2$ $b$ is $0$ then for $a=3$ $b$ goes from $1$ to $-1$ skipping $0$ when $a=4$ $b$ goes from $2$ to $-2$ skipping $\pm1$

i am not sure how to express the limits of summation for $b$ (because it skips like that)

1

There are 1 best solutions below

0
On BEST ANSWER

\begin{aligned}\sum_{1\leq i,j\leq n}{f\left(i-j\right)}&=\sum_{k=1-n}^{n-1}{\sum_{i-j=k}^{}{f\left(k\right)}}\\ &=\sum_{k=1-n}^{n-1}{\sum_{i=\max\left(1, k+1\right)}^{\min\left(n, n+k\right)}{f\left(k\right)}}\\ &=\sum_{k=1-n}^{n-1}{f\left(k\right)\left(\min\left(n,n+k\right)-\max\left(1,k+1\right)+1\right)}\\ \sum_{1\leq i,j\leq n}{f\left(i-j\right)}&=\sum_{k=1-n}^{n-1}{\left(n-\left\vert k\right\vert\right)f\left(k\right)}\end{aligned}