Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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)...$. –  laovultai 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
add comment

HINT:

Expand $$\sum_{n=m}^{m+N-1}h(n)$$ What do you know about $h$?

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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