# Summing a function using modulus. [closed]

The problem:

If the infinite sum of a function is known, how to find:

\begin{align*} \sum_{i\equiv 0 \mod m}f(x_0+i)=\\\\ f(x_0)+f(x_0+m)+f(x_0+2m)+f(x_0+3m)+\ldots \end{align*}

And if the finite sum of a function is known, how to find:

\begin{align*} \sum_{i\equiv 0 \mod m}^{i = {(x_0+\lfloor \frac{x-x_0+1}{m}\rfloor m)}}f(x_0+i)=\\\\ f(x_0)+f(x_0+m)+f(x_0+2m)+f(x_0+3m) &\quad +\ldots+f\left(x_0+\left\lfloor \frac{x-x_0+1}{m}\right\rfloor m\right) \end{align*}

Details:

If we know a function $f$ and we can find the sum of its terms (defined as $S_f$), how to find the sum, but jumping some factors (defined as $MS_f$, where M representes modular)?

What's the relation with the sum function ($S_f$)? (I think this uses the root of the unity, but don't know how.)

For example, if:

$$S_f=\displaystyle\sum_{i=1}^{\infty}f(i)=f(1)+f(2)+\ldots$$

with infinite terms, how to find

\begin{align*} MS_f(x_0,m)&=\sum_{i\equiv 0 \mod m}f(x_0+i)\\\\ & = f(x_0)+f(x_0+m)+f(x_0+2m)+f(x_0+3m)+\ldots \end{align*}

And if:

$$S_f(x)=\displaystyle\sum_{i=1}^{x}f(i)=f(1)+\ldots+f(x-1)+f(x),$$

how to find

\begin{align*} MS_f(x,x_0,m)&=\sum_{i\equiv 0 \mod m}^{i = {(x_0+\lfloor \frac{x-x_0+1}{m}\rfloor m)}}f(x_0+i)\\\\ & = f(x_0)+f(x_0+m)+f(x_0+2m)+f(x_0+3m) \\\\ &\quad +\ldots+f\left(x_0+\left\lfloor \frac{x-x_0+1}{m}\right\rfloor m\right) \end{align*}

where $(x_0+\lfloor \frac{x-x_0+1}{m}\rfloor m)$ is the ultimate term of the arithmetic progression $x_0+k\times m$ which not exceeds $x$.

Edited:

As Jacques Carette said, I think the answer is using something like:

$MS_f(x,x_0,m)=\displaystyle\sum_{i=0}^{m-1}a_iS_f(w^ix)$ or $\displaystyle\sum_{i=0}^{m-1}a_iS_f(w^i(x+x0))$

but I don't know exactly.

Example:

$$S_f=\sum_{i=1}^{\infty}\frac{x^{i-1}}{(i-1)!}=e^x, \quad f(i)=\frac{x^{i-1}}{(i-1)!}$$ \begin{align*} MS_f(x_0,m)=\sum_{i\equiv 0 \mod m}f(x_0+i)=\sum_{i\equiv 0 \mod m}\frac{x^{(x_0+i)-1}}{((x_0+i)-1)!}\implies\\\\ MS_f(3,2)=\sum_{i\equiv 0 \mod 2}\frac{x^{(3+i)-1}}{((3+i)-1)!}=\sum_{j=0}^{\infty}\frac{x^{3+2j-1}}{(3+2j-1)!}=\cosh (x)-1 \end{align*}

-

## closed as too localized by Gjergji Zaimi, Dan Petersen, Mariano Suárez-Alvarez♦, Yemon Choi, quidNov 29 '11 at 0:44

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

That you asked on math.SE and did not get answers (in one day!) there does not automatically mean you should ask here. Maybe next time you could ask first on tea.mathoverflow.net if the question fits MO? –  Mariano Suárez-Alvarez Nov 28 '11 at 18:48
Well it has been very difficult join to this community. I think I have good questions, with Mathematics interest (like said in faq). The truth is, I didn't asked here because I didn't get ansser in Math.SE, I asked here because I wanted too, I would like another different opinions. I had seen questions in Math.SE with over 30 votes with no answer and answered here. So, what's the problem? If I ask in Math.SE and write in the question, you close my question. I I ask there too and write in the question, you close my question. Do you hate the Math.SE, didn't like no cross platafform? –  GarouDan Nov 30 '11 at 10:19
If I need ask things here and just here (what's is annoying thing) tell me that I'll remember. But, but you may point in faq where is it? Or put there (not in meta) that's not a polite thing. Maybe I had been some agressive, but I think all community (even me, a beginner here) should opine to have a better site. –  GarouDan Nov 30 '11 at 10:23

In general, you cannot get anything from just knowing $S_f$, there is just too little information. Note also that your $M$ is really an operator on $f$, not $S_f$; to see this, think of $f(i)=1/i!$ then $S_f = e$. How will $M$ manipulate $e$ to get those sums?

On the other hand, looking at your actual example, it seems you might want to know about generating functions rather than general sums of sequences. That is entirely different.

And your 'I think it uses roots of unity' was indeed along the right track. Let's consider the case where $x_0=0, m=2$, which is classical: this is the 'even' part of a function, which you can compute with $\frac{S_{f}(x)+S_{f}(-x)}{2}$. For $x_0=1,m=2$, you get the odd part, via $\frac{S_{f}(x)-S_{f}(-x)}{2}$.

In general, you'll want a function that looks like $$\frac{1}{m}\Sigma_{i=0}^{m-1} a_i S_{f}(\omega^i x)$$ for some weights $a_i$ which are also simple functions of $\omega^i$, where $\omega$ is a primitive $m$-root of unity.

For example, in the case where your sequences are holonomic, there are powerful algorithms for dealing with these questions (and most of them are implemented in both Maple and Mathematica, AFAIK). See the book $A=B$ by Petkovsek, Wilf and Zeilberger for a good introduction, and then Richard Stanley's 2-volume Enumerative Combinatorics if you want more.

-
@JacquesCarette. I think you're right about the $S_f$ and $MS_f$. Your formula using $x_0=0$ and $m=2$ shows what I need. And you're right again when you say I'm looking for something like $MS_f(x,x_0,m)=\displaystyle\sum_{i=0}^{m-1}a_iS_f(w^ix)$. I already know this A=B book and it's really a good one, about the other I'm looking for. But isn't clear to me how to find this $a_i$'s, can you point something or a algorithm on the books to treat this? –  GarouDan Nov 28 '11 at 15:22

There is absolutely nothing that you can say in general about this problem without putting some additional restriction on the function $f$. Think about it: you can start with any collection of $m$ functions $f_i, 1\le i\le m$, each supported on a distinct residue class mod $m$, and then add them together to get a new function $f$. But because the choice of $f_i$'s is completely arbitrary there is nothing that you can say in general about the relationship between the summatory function of $f$ and the summatory function of one of the $f_i$'s. If you have a particular function or a particular class of functions in mind then there is a chance, but in general no.

-
@AH, What about if $f$ a polynomial or a analytic function. –  GarouDan Nov 28 '11 at 16:41
For a non-zero polynomial the series you asked about don't converge. For your question about the relationship between the partial sums there is a closed form solution for polynomials, so yes there is a relationship. –  Alan Haynes Nov 28 '11 at 17:17