Suppose $h$ is a function on $Z$ that is periodic with period N, that is $h(n+N)=h(n)$ for all $n$. How to prove: for any $m \in Z$, $\sum_{n=m}^{m+N-1} h(n) =\sum_{n=0}^{N-1} h(n)$. In other words, any sum over an interval of length $N$ yields the same result. This is problem from the area of linear algebra and is a homework
How to prove: for any $m \in Z$, $\sum_{n=m}^{m+N-1} h(n) =\sum_{n=0}^{N-1} h(n)$
-
0Why can't you tag it as `linear-algebra` by yourself? – 2010-11-11
-
0It might be a problem from linear algebra class but it has nothing to do with linear algebra. Not sure what would be a right tag though. – 2010-11-11
-
0@J. M.: Yes he/she could! – 2010-11-11
3 Answers
Let $m \in \{0 \dots, N-1\}$. Then we have $$\sum_{n=m}^{m+N-1} h(n) = \sum_{n=m}^{N-1} h(n) + \sum_{n=0}^{m-1} h(n + N) = \sum_{n=m}^{N-1} h(n) + \sum_{n=0}^{m-1} h(n) = \sum_{n=0}^{N-1} h(n)$$ Now for $m \in \mathbb{Z}$ write $m = kN + r$ with $k \in \mathbb{Z}$ and $r \in \{0, \dots, N-1\}$. We clearly have $$\sum_{n=kN+r}^{k(N+1) + r -1} h(n) = \sum_{n=r}^{N+r-1} h(n+kN) = \sum_{n=r}^{N+r-1} h(n)$$ Now the last expression equals $\sum_{n=0}^{N-1} h(n)$ by the first part of the argument.
-
0How do you get $\sum_{n=m}^{m+N-1} h(n) = \sum_{n=m}^{N-1} h(n) + \sum_{n=0}^{m-1} h(n)$? And why you it is must to make argument after the first argument? I mean $\sum_{n=kN+r}^{k(N-1)+r-1} h(n)...$. – 2010-11-11
-
0You just split the sum into two parts: those less than *N* and those greater or equal to N. The first part is already ok. The second part is in the for h(N+k), so you can use the periodicity assumption to bring it back to h(k). – 2010-11-11
-
0Regarding my argument... you certainly don't have to do it like that, you are free to come with proof of your own. But this seemed like a simple way to mee: first inspect the case where the summation interval is close to what you want to prove (i.e. [0, N-1]) and then use periodicity to transform any other interval (e.g. [2N +4, 3N + 3], with N > 4) into the one consider in the first part (in this case [4, N + 3]). – 2010-11-11
HINT:
Expand $$\sum_{n=m}^{m+N-1}h(n)$$ What do you know about $h$?
The important point here is that any set of $N$ consecutive integers is a complete residue system modulo $N$. See complete residue system. We consider the index modulo $N$ since $h(n)$ has period $N.$ i.e. the numbers $ \lbrace m,m+1,m+2,\ldots,m+N-1 \rbrace $ modulo $N$ are $ \lbrace 0,1,2,\ldots,N-1 \rbrace $ in some order.
Your identity follows immediately from this fact.