0
$\begingroup$

As I was reading my book, I came across the following expression: \begin{equation} \sum _{n=-N}^N\sum _{m=-N}^N \phi \left(n-m\right) \end{equation} Then the book said, if we let $k = n-m$, then: \begin{equation} \sum _{k=-2N}^{2N}\left(1-\frac{\left|k\right|}{2N+1}\right)\phi \left(k\right) \end{equation}

Can somebody please tell me if this is a property of summation operator and how they got there. Also please refer me to a reference that carries such properties of summation. Thank you in advance.

$\endgroup$
7
  • 3
    $\begingroup$ Are you sure you have that right? Given your top line, I get a second line of $\sum_{k=-2N}^{2N} (2N + 1 - |k|)\phi(k)$. This can be arrived at just by thinking logically about how many occurrences there are of $n-m = -2N$, how many occurrences there are of $n-m = -2N + 1$, and so on, and then writing the summation accordingly. $\endgroup$
    – TimWescott
    Aug 30, 2020 at 23:42
  • $\begingroup$ The equation must be wrong, since $|k|/(2N+1)$ can be non-integer. $\endgroup$
    – MBaz
    Aug 31, 2020 at 1:14
  • $\begingroup$ Thank you very much for your comments. Yes, this was straight away from my book. Unfortunately I have been puzzled by it for quite sometime. $\endgroup$
    – JordenSH
    Aug 31, 2020 at 2:32
  • $\begingroup$ @MBaz: Non-integer is fine I'd say. $\endgroup$
    – Matt L.
    Aug 31, 2020 at 8:02
  • $\begingroup$ @MattL. Hm... Let $N=2$ for example. Then, the original sum contains one single term where $m-n=4$, and it is $\phi(4)$. In the OP's simplified equation, there is one single term with $k=4$, and it is $\frac{1}{5}\phi(4)$. How can the two sums be equal? $\endgroup$
    – MBaz
    Aug 31, 2020 at 13:45

2 Answers 2

1
$\begingroup$

That equation is almost correct. Tim gave the correct solution in a comment, which is just a scaled version of the given formula. I'd like to show how you can quite easily see this.

First, note that

$$\sum_{m=-N}^N\phi(n-m)=(r\star\phi)(n)\tag{1}$$

where $\star$ denotes convolution, and $r(n)$ is a sequence of ones in the range $n\in[-N,N]$. Second, summing a sequence is also a convolution with the sequence $r(n)$ evaluated at $n=0$. So we can write

$$\begin{align}\sum_{n=-N}^N\sum_{m=-N}^N\phi(n-m)&=(r\star r\star\phi)(n)\Big|_{n=0}\\&=(s\star\phi)(n)\Big|_{n=0}\tag{2}\end{align}$$

where $s(n)$ is the convolution of two rectangular sequences, which is a triangular sequence:

$$s(n)=(2N+1)\left[1-\frac{|n|}{2N+1}\right],\qquad n\in[-2N,2N]\tag{3}$$

Combining $(2)$ and $(3)$ gives the desired result, which equals the formula in your question, scaled by $2N+1$.

$\endgroup$
2
  • $\begingroup$ Thank you very much for your answer. However, I hardly think the problem is of that regards. The problem is merely of proving the form \begin{equation}\sum _{n\:=a}^b\left(n\right)\:\sum _{n\:=a}^b\left(n\right) \end{equation} $\endgroup$
    – JordenSH
    Sep 2, 2020 at 4:25
  • $\begingroup$ @Raykh: Both answers show how the formula in your question is obtained (apart from a scaling factor), so I'm not sure I understand your comment. $\endgroup$
    – Matt L.
    Sep 2, 2020 at 6:48
0
$\begingroup$

Since $n$ and $m$ are integers in $[-N,N]$, $n-m$ can take any value in $[-2N,2N]$. The problem is: how many occurrences of the same index value $n-m$ can we find?

For instance, $n-m=0$ when $n=m$: between $-N$ and $N$, we have $2N+1$ options, hence $(2N+1)$ of the $\phi(0)$. For $n-m=1$, $m=n-1$. For $n=-N$, there is no solution for $m$, but you have only $2N$ possibilities. By symmetry, you will have the same for $n-m=-1$. Hence
$2N$ times $\phi(1)$ and $\phi(1)$. You can convince yourself (by induction) that each time you increase the offset $|n-m|$ by one, you get one less possibility. Finally, there is only one case where $|n-m| = 2N$.

Therefore, the integer weights for $\phi(\cdot)$ are a triangular, Bartlett or Fejér window:

$$ [1,\,2,\,\ldots,2N+1\,,\ldots,2,1]\,. $$

Such counting are quite common with sequences that partly overlap with a varying offset, especially on spectral estimation and periodogram-like estimation.

$\endgroup$
2
  • $\begingroup$ Thank you very much for your answer. However, I hardly think the problem is of that regards. The problem is merely of proving the form \begin{equation}\sum _{n\:=a}^b\left(n\right)\:\sum _{n\:=a}^b\left(n\right) \end{equation} $\endgroup$
    – JordenSH
    Sep 2, 2020 at 4:27
  • $\begingroup$ There are several types of proofs. Some can be algebraic, combinatoric, etc. I believe that this answer is a form of proof "by counting", underlying the "diagonal" argument on the indices. The integer weights provide the same answer, and the reasoning can be reused for other sums, with elementary tools $\endgroup$ Sep 2, 2020 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.