Tuesday 16 July 2013

summation - Sum of a series involving modulus operator



I'm attempting to work out a problem that involves summing a series of numbers. I know the formula to find each element of the series, but I do not know how to use this to make an equation for the series, or find the sum. The equation for each term of the series is this



$$
a_n = (n * \frac{n+1}{2}) mod 10
$$




Because of the modulus operator, I'm completely unsure of how to really work with this, as I have little experience with it. I'm not familiar with it beyond knowing what the operation actually does.


Answer



As André Nicolas pointed out in his comment, sequence $a_n$ is periodic, with period $20$.



This can be seen easily: $$a_{n+20} =\frac{n^2+41n+420}{2}\bmod 10=\frac{n(n+1)}{2}\bmod 10+(20n+210)\bmod 10=a_n+0$$



(if we want to be formal, we've only proved that the sequence repeats with period $20$, but didn't rule out the possibility of it repeating with some smaller period)



Thus, the sum of first $M$ terms of the sequence can be evaluated by looking at blocks of $20$ consecutive numbers first (sum of each such block equals $70$) and then adding the remaining terms explicitly:




$$\sum_{i=0}^M a_i = 70\left\lfloor\frac{M}{20}\right\rfloor + \sum_{i=0}^{M\ \bmod \ 20}a_i$$



Technically, it's possible to find an explicit expression for the latter (finite) sum, but it's most likely going to be rather unwieldy.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...