# Summing a function using modulus

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

Maybe:

$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*}

-
And what is $f$? –  Dimitrije Kostic Nov 26 '11 at 2:49
Please don't use non-standard abbreviations (such as "AP") without any indication of what they mean; especially not on the subject. Thank you. –  Arturo Magidin Nov 26 '11 at 2:52
@DimitrijeKostic, I think we can define $f$ as a known analytic function. But I'm searching a answer for a generic known function. The main problem here if we know how to compute a sum of amount of terms, how can we find this sum but jumping some steps? –  GarouDan Nov 26 '11 at 3:11
@ArturoMagidin I'll remember. But in english this isn't a estabilished term? For example, in Wikipedia we have AP. –  GarouDan Nov 26 '11 at 3:11
$q$-series doesn't mean what you think it means. –  Ｊ. Ｍ. Nov 26 '11 at 4:34

In the comment at your question I mentioned Bernoulli-polynomials; in fact I approach such problems using a variant which I call "zeta-polynomials". These are that polynomials that originally were used by Bernoulli and Faulhaber for the sums-of-like-powers and actually are the integrals of the Bernoulli-polynomials. I'll reflect my type of proceeding here only cursory but I think it will be sufficient to show the principle.

Ingredients are a matrix-notation, the concept of indefinite summation and two standard-matrices: the upper triangular standard Pascalmatrix P and the Z-matrix which contains the coefficients of the zeta-polynomials. For the algebra with formal power series I denote their coefficients in a vector, say A and the powers of x in some vector V(x) of "vandermonde-type", such that always $\small V(x)=[1,x,x^2,x^3,x^4,...]$. Then, if your function f(x) has a power series representation, its coefficients may be assumed in a vector A, thus we'll have f(x) denoted by the dot-product
$$\small f(x) = V(x) \cdot A$$
Now the pascalmatrix P comes into play. Since it is upper triangular we have the identity $$\small V(x) \cdot P = V(x+1)$$ due to the binomial-theorem applied to all nonnegative integer powers and in generalization $$\small \begin{eqnarray} V(x) \cdot P &=& V(x+1) \\ V(x) \cdot P^2 &=& V(x+2) \\ V(x) \cdot P^3 &=& V(x+3) \\ \ldots \\ V(x) \cdot P^h &=& V(x+h) \\ \end{eqnarray}$$ On the other hand, your problem is first, to find the sum $$\small S(1,n)=V(1) \cdot A + V(2)\cdot A + V(3) \cdot A + \cdots V(n)\cdot A= \sum_{k=0}^{n-1} f(1+k)$$ For finite sums it is obvious how to rewrite this using sums of powers of of P: $$\small S(1,n)=V(1) \cdot (I + P + P^2 + \ldots + P^{n-1}) \cdot A$$

Now the idea of Bernoulli to introduce polynomials for the sum-of-like-powers can elegantly be modeled by this approach. We provisorically assume the possibility of some matrix Z which represents the geometric series of powers of P: $$\small Z = I+ P + P^2 + \ldots = (I - P)^{-1}$$ which then would allow to write $$\small T(a)=V(a) \cdot \left( I + P + P^2 + \ldots + P^n + \cdots \right) \cdot A = V(a) \cdot Z \cdot A = \sum_{k=0}^\infty f(a+k)$$ and then $$\small S(a,b) = T(a) - T(b+1) = (V(a)-V(b+1) )\cdot Z \cdot A = \sum_{k=a}^b f(k)$$
The clue is now, that such a matrix Z in fact can be found and just contains the mentioned zeta-polynomials (or integrals of Bernoulli-polynomials) and is a not-strictly upper-triangular variant of P (it contains one additional subdiagonal).
The evaluation for the coefficients of the resulting formal power-series for S(a,b) by the evaluation of the dot product $\small F=Z \cdot A$ includes now in many cases the summation of divergent series but can also be rewritten in terms of the Euler-MacLaurin-series.

The generalization to bigger steps than 1 (in your example m>1 can then simply be expressed by the introduction of the m'th power of P instead of P and a similarity-transform of the Z by just $\small Z_m = V(m) \cdot Z \cdot V(1/m)$ (where the V() are taken as diagonal-matrices. Since Z is column-finite this is also well defined.
What you get by this tiny pieces of matrix-algebra is the expression of your problem in terms of a series whose coefficients are polynomials involving zeta-values at nonpositive integers or better known: of the bernoulli-numbers.

I've described that procedere at many and various places and don't know at the moment which would be the best example. Here is a text about it, still in an unfinished draft-mode. And here is the text, where I initially described the matrix Z of zeta-polynomials and which might give a further clue (relevant pages 14..19). Also here on MSE you might search for hte keyword of "indefinite summation" (or even in Wikipedia) to find more hints in more common notation.

-
I need take a better look in your solution but looks like this works fine. Thx. –  GarouDan Nov 30 '11 at 1:17

Agree with others on that your question is too broad, and no general formula is there. The way you phrased the question means (among other things) that given, for example, that $$1= a_0+a_1+a_2+\cdot$$ you ask for the value of the sum $$a_1+a_3+a_5+\cdots?$$ This is so obviously impossible: after all the $a_i$:s could be all zero starting from the second, it might be that $a_i=2^{-i}$, it might be that $a_i=6/(\pi i^2),\ldots$. Consequently we all had to put some effort in trying to guess what did you really want to ask.

My best guess is that you are only interested in power series (judging from your example with $e^x$ and $\cosh x$). If that is so, then something like the following may be useful to you? If the Maclaurin series $$f(x)=\sum_{n=0}^\infty a_n x^n$$ converges in some circle about the origin, and $\zeta$ is a root of unity of order $m$, then for all integers $k, 0\le k <m$ we have $$f(\zeta^k x)=\sum_{n=0}^\infty a_n (\zeta^k)^n x^n=\sum_{\ell=0}^{m-1}\zeta^{k\ell}\sum_{j=0}^\infty a_{\ell+jm}x^{\ell+jm},$$ where I wrote $n=\ell+jm$ in the last step and grouped the terms according to the power of $\zeta$ that appears as a factor.

The usual sums involving $n$th roots of unity (or discrete Fourier transform, if you prefer that term) then show that $$\sum_{k=0}^{m-1}\frac{\zeta^{-k\ell}}m f(\zeta^k x)=\sum_{n\ge0, n\equiv \ell\pmod{m}}a_nx^n.$$ Your $e^x$ vs. $\cosh x$ example arises as the case $m=2$, $\zeta=-1$, $\ell=0$, $a_n=1/n!$.

-
Thx. This multisection formula, if I consider the $a_n$ a sequence and I know the sum of powers in x, as you said. And take the limit of x to 1, this can works fine. –  GarouDan Nov 30 '11 at 1:20

(My apologies if this is more of a comment than an answer, but I don't have the ability to leave comments yet)

As I understand it, you're hoping to express your sum in the form

$$S=g\left( S_f(a_1, b_1), S_f(a_2, b_2), S_f(a_3, b_3), \dots, S_f(a_j, b_j) \right)$$

for some $g$ and some choice of the $a$ and $b$, where $j$ is significantly smaller than $\frac{b-a}{m}$. In general, I don't think this is possible without further assumptions. If $j$ is much smaller than $m$ there will always be a $k$ such that neither $a+i+km$ and $a+i+km+1$ appear at the end of one of your $j$ intervals. In that case you can replace $\{f(a+i+km), f(a+i+km+1)\}$ by $\{f(a+i+km)+\epsilon, f(a+i+km+1)-\epsilon\}$ and change the left side but not the right side.

I think what you're thinking of is the situation where you know not only $S_f(a,b)$ but $$S_f(a,b,x)=\sum_{i=a}^b f(i) x^i$$ In that case you can extract the sum you want by considering $S_f(a,b,x)$ for $x$ being various $m^{th}$ roots of unity.

-
Thx about the explanation. I would like sum just some values of a function, when you say $\sum_{i=a}^{b}f(i)x^i$ isn't correct. But I don't know if this is really possible. Probably I will edit to make this more clear and what the purpose. –  GarouDan Nov 28 '11 at 11:10