5
$\begingroup$

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?

  • 0
    @Didier Piau : thank you very much for the answer.2011-04-07

1 Answers 1

3

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.