# How to prove: for any $m \in Z$, $\sum_{n=m}^{m+N-1} h(n) =\sum_{n=0}^{N-1} h(n)$

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

-
Why can't you tag it as linear-algebra by yourself? – J. M. Nov 11 '10 at 10:46
It 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. – Marek Nov 11 '10 at 11:09
Maybe you should consider accepting some of the answers to your questions? – AD. Nov 11 '10 at 11:29
@J. M.: Yes he/she could! – AD. Nov 11 '10 at 11:31

## 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.

-
How 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)...$. – alvoutila Nov 11 '10 at 11:47
You 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). – Marek Nov 11 '10 at 13:23
Regarding 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]). – Marek Nov 11 '10 at 13:27

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.

-