# a question on summation expansion

Q1.

$$\sum\limits_{j=0}^{N-1} \sum\limits_{i=0}^{N-1} \sum\limits_{y=0}^{j} \sum\limits_{x=0}^{i} a(x)a(y)b(|x-y|)$$

Given that $b(0) = 0$, Find the coefficient of $b(k)$, $0\le k \le N-1$ in the above expansion.

Q2. $$\sum\limits_{j=0}^{N-1} \sum\limits_{i=0}^{N-1} \sum\limits_{x=0}^{\min(i,j)} a(x) .$$

Find the coefficient of $a(x)$ in the above expansion?

-
Is this homework? – Brian Mar 16 '11 at 12:36
You've been a member for over 4 months now. Yet you are still making posts (i) in the imperative mode; and (ii) with no motivation. – Arturo Magidin Mar 16 '11 at 19:02
Did you get something out of the answer below? – Did Apr 7 '11 at 8:23
@Didier Piau : thank you very much for the answer. – Rajesh Dachiraju Apr 7 '11 at 10:04

Let us use a general approach. A first principle to evaluate multiple sums is:

When dealing with multiple sums, see what happens when exchanging the order of the summations.

Re Q2, this means writing the sum $S$ as a sum over $x$ of $a(x)$ times a sum over $i$ and $j$.

Which brings us to a second general principle:

Sums over a fixed set of integers are easier.

And to the most useful tool to apply this principle:

Write the spans of sums as indicator functions.

In this context, some people use Iverson bracket $[\mathfrak A]$ to mean $1$ if assertion $\mathfrak A$ is true and $0$ otherwise, and I will use this convention. For instance, still Re Q2, $$S=\sum_{j=0}^{N-1}\sum_{i=0}^{N-1}\sum_{x=0}^{N-1}[x\le \min\{i,j\}]\cdot a(x).$$ But $[x\le \min\{i,j\}]=[x\le i]\cdot[x\le j]$, hence exchanging the order of the summations yields $$S=\sum_{x=0}^{N-1}a(x)\sum_{i=0}^{N-1}[x\le i]\sum_{j=0}^{N-1}[x\le j].$$ The sum over $i$ and the sum over $j$ coincide and their common value is $$\sum_{j=0}^{N-1}[x\le j]=\sum_{j=x}^{N-1}[x\le j]=N-x,$$ hence $$S=\sum_{x=0}^{N-1}(N-x)^2a(x).$$ This solves Q2.

The solution for Q1 is somewhat more involved, but I suggest that you now see how far you can go with these principles to try to solve it.

-