1
$\begingroup$

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

  • 0
    Why can't you tag it as `linear-algebra` by yourself?2010-11-11
  • 0
    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.2010-11-11
  • 0
    @J. M.: Yes he/she could!2010-11-11

3 Answers 3

1

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.

  • 0
    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)...$.2010-11-11
  • 0
    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).2010-11-11
  • 0
    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]).2010-11-11
1

HINT:

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

1

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.