# how to calculate sum and term of recurring series involving Floor

The recurrence series is given by $$t_{n+1} = t_n + 2\left\lfloor{n -1 \over 4} +1\right\rfloor , \; t_0 = 1$$

What would be the closed form of $t_n$ in terms of $n$ and it's sum up to $n$ terms? The sequence generated can be found on here on OEIS.

-
What's the initial value, say $t_0$ or $t_1$? – Patrick Li Sep 29 '12 at 13:13
@PatrickLi sorry ... the value of $t_0 = 1$ – Monkey D. Luffy Sep 29 '12 at 13:15

First note that the sequence of $2\lfloor \frac{n-1}{4} + 1 \rfloor$ is $$2, 2, 2, 2, 4, 4, 4, 4, 6, 6, 6, 6, \dots$$

For any integer $n$, let $k$ be the largest integer such that $4k \leq n$. In other words, $k=\lfloor \frac{n}{4}\rfloor$.

First we sum over the first $4k$ terms which gives us $$4\times 2 + 4\times 4 + \dots + 4\times 2k = 8(1+2+\dots + k) = 4k(k+1)$$

Next let's add the remaining terms from $4k+1$ to $n$. There are $n-4k$ terms,each of them being $2(k+1)$. So the final result is $$4k(k+1)+2(n-4k)(k+1)+1$$ where the last value of $1$ comes from the initial value $t_0=1$.

-

Ignore $t_0$ and $t_1$, the first terms $-1$ are: $\;(1\cdot2)\;(2\cdot2)\;(3\cdot2)\;(4\cdot2)\;(3\cdot4)\;(4\cdot4)\;(5\cdot4)\cdots$ which suggests:$$t_{n}=2{\lfloor\frac{n-1}{4}+1\rfloor}\cdot \left(n-1-2\lfloor\frac{n-1}{4}\rfloor\right)+1$$

(this looks more complicated than it actually is)

Note that when $n$ is a multiple of $4$ we have $\lfloor\frac{n-1}{4}\rfloor=\lfloor\frac{n}{4}-1\rfloor$ and otherwise $\lfloor\frac{n-1}{4}\rfloor=\lfloor\frac{n}{4}\rfloor$

$\bullet\;\;n$ multiple of $4:$

$$t_{n+1}=2{\lfloor\frac{n}{4}+1\rfloor}\cdot \left(n-2\lfloor\frac{n}{4}\rfloor\right)+1=2{\lfloor\frac{n}{4}\rfloor}\cdot \left(n-2\lfloor\frac{n}{4}\rfloor\right)+n+1$$

$$=2{\lfloor\frac{n}{4}\rfloor}\cdot \left(n-2\lfloor\frac{n}{4}\rfloor\right)+2{\lfloor\frac{n}{4}\rfloor}\cdot 2+1=2{\lfloor\frac{n}{4}\rfloor}\cdot \left(n+2-2\lfloor\frac{n}{4}\rfloor\right)+1$$

$$=2{\lfloor\frac{n}{4}\rfloor}\cdot \left(n-1-2\lfloor\frac{n}{4}-1\rfloor\right)+2\lfloor\frac{n}{4}\rfloor+1$$$$=2{\lfloor\frac{n-1}{4}+1\rfloor}\cdot \left(n-1-2\lfloor\frac{n-1}{4}\rfloor\right)+2\lfloor\frac{n-1}{4}+1\rfloor+1$$ $$=t_n+2\lfloor\frac{n-1}{4}+1\rfloor$$

$\bullet\;\;n$ not a multiple of $4:$

$$t_{n+1}=2{\lfloor\frac{n}{4}+1\rfloor}\cdot \left(n-2\lfloor\frac{n}{4}\rfloor\right)+1=2{\lfloor\frac{n-1}{4}+1\rfloor}\cdot \left(n-2\lfloor\frac{n-1}{4}\rfloor\right)+1$$

$$=2{\lfloor\frac{n-1}{4}+1\rfloor}\cdot \left(n-1-2\lfloor\frac{n-1}{4}\rfloor\right)+2\lfloor\frac{n-1}{4}+1\rfloor+1=t_n+2\lfloor\frac{n-1}{4}+1\rfloor$$

This verifies our assumption. The sum was nicely done by Patrick Li so I'll leave it there.

-