4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ There is a closed form with a bunch of floor functions. $\endgroup$ – Claude Leibovici Jan 8 at 9:52
  • $\begingroup$ 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. $\endgroup$ – 5xum Jan 15 at 8:49
  • $\begingroup$ @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. $\endgroup$ – Elementary Jan 15 at 9:03
4
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ How about $b_k=\lfloor1+\lfloor{k\over3}\rfloor-{k\over3}\rfloor$? $\endgroup$ – Barry Cipra Jan 8 at 10:10
  • $\begingroup$ @BarryCipra That works, yeah. I added it to my answer (hope you don't mind) $\endgroup$ – 5xum Jan 8 at 10:22
  • $\begingroup$ My pleasure. But you mean $b_k$, not $b_n$. $\endgroup$ – Barry Cipra Jan 8 at 10:25
  • $\begingroup$ And What exactly is the result? $\sum_{i=1}^{n}a_n$ $\endgroup$ – Elementary Jan 8 at 11:24
  • $\begingroup$ @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$$ $\endgroup$ – Barry Cipra Jan 8 at 12:10
1
$\begingroup$

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

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

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 ?

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

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

$\endgroup$
  • $\begingroup$ I think, if there is an exist a closed form, it should be expressed by floor function. $\endgroup$ – Elementary Jan 8 at 9:26
  • $\begingroup$ @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. $\endgroup$ – Anurag A Jan 8 at 9:29
  • $\begingroup$ No, I didn't do this. $\endgroup$ – Elementary Jan 8 at 9:32
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.