# Algebraic Closed Form for $\sum_{n=1}^{k}\left( n- 3 \lfloor \frac{n-1}{3} \rfloor\right)$

Let's look at the following sequence:

$$a_n=\left\{1,2,3,1,2,3,1,2,3,1,2,3,...\right\}$$

I'm trying to calculate:

$$\sum_{n=1}^{k} a_n$$

Attempts:

I have a Closed Form for this sequence.

$$a_n=n- 3 \bigg\lfloor \frac{n-1}{3} \bigg\rfloor$$

The problem is, I'm looking for a closed form for this summation:

$$\sum_{n=1}^{k}\left( n- 3 \bigg\lfloor \frac{n-1}{3} \bigg\rfloor\right)$$

Is it possible?

• There is a closed form with a bunch of floor functions. – Claude Leibovici Jan 8 at 9:52
• You recieved 5 answers to your question. Is any of them what you needed? If so, you should upvote all the useful answers and accept the answer that is most useful to you. – 5xum Jan 15 at 8:49
• @5xum I've been upvote before. Now, I accept. By the way, If you add the most recent result to your answer, it will be perfect. Regards. – Elementary Jan 15 at 9:03

## 5 Answers

Writing down a couple of the sums:

$$1,3,6,7,9,12,13,15,18,\dots$$

and comparing that to the sequence$$1,3,5,7,9\cdots$$

gives you a clue that the difference between the arithmetic sequence and the sequence you want to describe is simply $$0,0,1,0,0,1,0,0,1,0,0,1\dots$$ which is a sequence you can describe in closed form in a way similar to $$a_n$$.

That is, you can see that $$\sum_{i=n}^k a_n = 2k-1 + b_k$$

where $$b_k$$ is equal to $$1$$ if $$k$$ is divisible by $$3$$ and $$0$$ otherwise.

You can express $$b_n$$ algebraically by taking $$a_n$$ and any function for which $$f(1)=f(2)=0$$ and $$f(3)=1$$, and you have $$b_n=f(a_n)$$.

I can't think of any "elegant" function $$f$$ at the moment, but a quadratic polynomial can surely do it, since we only have a restriction on three points. The quadratic polynomial that satisfies $$f(1)=f(2)=0$$ and $$f(3)=1$$ is $$f(x)=\frac12x^2-\frac32 x + 1.$$

Edit:

Thanks to BarryCipra, a nicer function (more in the spirit of your solution) for $$b_k$$ is

$$b_k = \left\lfloor 1 + \left\lfloor\frac k3\right\rfloor - \frac k3\right\rfloor$$

• How about $b_k=\lfloor1+\lfloor{k\over3}\rfloor-{k\over3}\rfloor$? – Barry Cipra Jan 8 at 10:10
• @BarryCipra That works, yeah. I added it to my answer (hope you don't mind) – 5xum Jan 8 at 10:22
• My pleasure. But you mean $b_k$, not $b_n$. – Barry Cipra Jan 8 at 10:25
• And What exactly is the result? $\sum_{i=1}^{n}a_n$ – Elementary Jan 8 at 11:24
• @Beginner, a complete answer is $$\sum_{n=1}^ka_n=2k-1+\left\lfloor 1 + \left\lfloor\frac k3\right\rfloor - \frac k3\right\rfloor$$ Is that what your comment is asking for? If you like, it can be simplified to $$\sum_{n=1}^ka_n=2k+\left\lfloor \left\lfloor\frac k3\right\rfloor - \frac k3\right\rfloor$$ – Barry Cipra Jan 8 at 12:10

Subtracting the "average" sequence

$$2,2,2,2,2,2,2,2,2,\cdots$$ you get

$$-1,0,1,-1,0,1,-1,0,1,\cdots$$

which sums as a periodic one

$$-1,-1,0,-1,-1,0,-1,-1,0,\cdots$$

The latter can be expressed as

$$\frac{(n-1)\bmod3-n\bmod 3-2}3.$$

So globally,

$$2n+\frac{(n-1)\bmod3-n\bmod 3-2}3.$$

• (+1) , It would be great if we found a closed form that could be expressed by the floor function – Elementary Jan 8 at 9:43
• @Beginner: modulo and floor are interchangeable, with simple arithmetic. – Yves Daoust Jan 8 at 9:46

If you consider$$b_k=\sum_{n=1}^{k}\left( n- 3 \bigg\lfloor \frac{n-1}{3} \bigg\rfloor\right)$$ you could see, after some simple manipulationd that it corresponds to the recurrence relation $$b_k=b_{k-1}+b_{k-3}-b_{k-4}\qquad \text{with}\qquad b_1=1, b_2=3, b_3=6, b_4=7$$ Using the conventional method you should end with $$b_k=2k-\frac{2}{3} \left(1-\cos \left(\frac{2 \pi k}{3}\right)\right)$$

Edit

If you enjoy the floor function, using a CAS, I got for $$b_k$$ the small monster $$\frac{1}{2} \left(k^2+k-3 \left\lfloor \frac{k}{3}\right\rfloor ^2-3 \left\lfloor \frac{k-2}{3}\right\rfloor \left(\left\lfloor \frac{k-2}{3}\right\rfloor +1\right)-3 \left\lfloor \frac{k-1}{3}\right\rfloor \left(\left\lfloor \frac{k-1}{3}\right\rfloor +1\right)+3 \left\lfloor \frac{k}{3}\right\rfloor \right)$$

Which one do you prefer ?

• Of course, Floor function :) – Elementary Jan 8 at 10:06
• @Beginner. Joke or serious ? – Claude Leibovici Jan 8 at 10:09
• Both are beautiful. :) Thank you very much (+) – Elementary Jan 8 at 10:34

If $$n \equiv 0 \pmod{3}$$, i.e. say $$n=3s$$ (where $$s \geq 1$$), then $$a_n=3s-3\lfloor s-\frac{1}{3}\rfloor=3s-3(s-1)=3$$.

If $$n \equiv 1 \pmod{3}$$, i.e. say $$n=3s+1$$ (where $$s \geq 0$$), then $$a_n=3s+1-3\lfloor s\rfloor=1$$.

If $$n \equiv 2 \pmod{3}$$, i.e. say $$n=3s+2$$ (where $$s \geq 0$$), then $$a_n=3s+2-3\lfloor s+\frac{1}{3}\rfloor=2$$.

So depending on what $$k$$ is we can count the number of terms which are $$1's$$, $$2's$$ and $$3's$$.

For $$k=1,2$$, the sum will be $$\color{red}{1}$$ and $$\color{red}{3}$$, respectively. So for $$k \geq 3$$, we do the following:

If $$k=3t$$ for $$t \geq 1$$, then $$\sum_{n=1}^k\left(n-3\left\lfloor n-\frac{1}{3}\right\rfloor\right)=\sum_{n=1}^{3t}\left(n-3\left\lfloor n-\frac{1}{3}\right\rfloor\right)=t(1+2+3)=6t=\color{blue}{2k}.$$

If $$k=3t+1$$ for $$t \geq 1$$, then $$\sum_{n=1}^k\left(n-3\left\lfloor n-\frac{1}{3}\right\rfloor\right)=\sum_{n=1}^{3t+1}\left(n-3\left\lfloor n-\frac{1}{3}\right\rfloor\right)=t(1+2+3)+1=6t+1=\color{blue}{2k-1}.$$

Likewise we can get the expressions for $$k=3t+2$$ as $$\sum_{n=1}^k\left(n-3\left\lfloor n-\frac{1}{3}\right\rfloor\right)=\sum_{n=1}^{3t+2}\left(n-3\left\lfloor n-\frac{1}{3}\right\rfloor\right)=t(1+2+3)+(1+2)=6t+3=\color{blue}{2k-1}.$$

• I think, if there is an exist a closed form, it should be expressed by floor function. – Elementary Jan 8 at 9:26
• @Beginner you are summing up to $k$ terms, so the answer is a function of $k$. I am not sure what you mean by the closed form has to be in terms of floor function. – Anurag A Jan 8 at 9:29
• No, I didn't do this. – Elementary Jan 8 at 9:32

Sorry can't comment on @5xum's answer. Building on the quadratic function we can derive: $$S_k=\frac{1}{2}((k-3\lfloor\frac{k}{3}\rfloor)^2+k+9\lfloor\frac{k}{3}\rfloor)$$, which is pretty neat.

To derive this, note that from @5xum's answer, $$S_k=2k-1+\frac{1}{2}(x^2 -3x+2)$$ where $$x=k-3\lfloor\frac{k}{3}\rfloor$$. We can write $$k=x+3\lfloor\frac{k}{3}\rfloor$$, so that: $$S_k=\frac{1}{2}(x^2 -3x+2+4x+12\lfloor\frac{k}{3}\rfloor-2)=\frac{1}{2}(x^2+x+12\lfloor\frac{k}{3}\rfloor).$$ Substituting $$x$$ back yields the result.