2
$\begingroup$

I am having difficulty proving that \begin{align} \sum_{i = 0}^{M-1} \sum_{j = 0}^{N - 1} \delta \left[a - \left(Ni + j\right)\right] = 1 \end{align} for $M < N$ and $0 \leq a < NM$. Where $\delta[n] = 1$ for $n = 0$ and $\delta[n] = 0$ otherwise. I guess I am mainly struggling with how to concisely show that $Ni + j$ takes on every value from $[0,1,\ldots,NM-1]$ exactly once during the double summation.

How does one show this convincingly starting with the original summation? I was reading a paper on non-uniform sampling theory and a similar expression with Dirac delta distributions where used, but the argument provided was mostly qualitative and I was looking for something with a little more detail.

2 Answers 2

3

If $a=Ni+j$ with $j$ in the set $F=\{0,1,\ldots,N-1\}$ and $i$ integer, then $Ni+j$ is the Euclidean division of $a$ by $N$. If $0\leqslant a\leqslant NM-1$, indeed the quotient $i$ of the Euclidean division of $a$ by $N$ is in the set $E=\{0,1,\ldots,M-1\}$.

To summarize, there exists exactly one $(i,j)$ in the set $E\times F$ such that $a=Ni+j$ hence the double sum evaluates at $1$.

  • 0
    Great observation. I did not notice the division algorithm relationship between $a$ and $N$, but it seems quite obvious now. Thanks.2012-09-22
2

If you take the sequence $Ni+j$ for a fixed $i$ and $j=0,\ldots,N-1$,

$ Ni+0,\ldots,Ni+N-1, $

you see that the last term is $1$ unit less that than the first term of the next sequence for $i+1$

$ N(i+1)+0,\ldots,N(i+1)+N-1, $

so two successive sequences for fixed $i$ have no common value.