Find closed form for $1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, \ldots$

Question

Is there any closed form for the following?

$$1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, 10, \ldots$$

I tried to find one, but I failed.

I saw solution on Wolfram Alpha, but I didn't understand it:

Generating function: $$\mathcal G_n(a_n)(z)=\dfrac{z+1}{(z-1)^2(z^2+z+1)}$$

What does that function mean, and how does it give me the solution to my question?

Answer 1

$$n-\left\lfloor\frac{n}3\right\rfloor$$

Answer 2

Although Did gave you a very nice closed form, I'll explain a bit about what Wolfram|alpha gave you. A generating function $f$ for a sequence $\{a_k\}_{k = 0}^{\infty}$ is the formal power series defined by $$ f(z) = \sum_{k = 0}^{\infty}a_k z^k. $$ So, a generating function for $\{a_k\}$ does not give you the $n$-th term of the sequence when you plug in $n$ - that's what the closed form does. Rather, the generating function encodes information about your sequence by using the terms as coefficients. Generating functions can be used to solve counting problems and to come up with closed forms for sequences; I don't know of any really good references for generating functions, but I'm sure someone can guide you in the right direction if that's what you're interested in.

It's often desirable to have a closed form for the function $f$ rather than just the series, and it appears your sequence has a generating function with a relatively nice closed form, so that's what Wolfram|alpha gave you. If you write out the series explicitly and perform some careful manipulations, you'll find that $$ 1 + 2z + 2z^2 + 3z^3 + 4z^4 + 4z^5 + 5z^6 + \dots = \frac{z + 1}{(z - 1)^2(z^2 + z + 1)}. $$ (For some region around the origin and provided Wolfram didn't mess up!)

Edit: Here's the way I would derive the generating function for your sequence. The following calculation is formal, and without regard for convergence - as it usually is with generating functions. \begin{align*} G(z) &= 1 + 2z + 2z^2 + 3z^3 + 4z^4 + 4z^5 + 5z^6 + \dots\\ &= 1 + z + z^2 + \ldots + z(1 + z + 2z^2 + 3z^3 + 3z^4 + 4z^5 + \dots)\\ &= \frac{1}{1 - z} + z(1 + z + z^2 + z^3 + \dots) + z(z^2 + 2z^3 + 2z^4 + 3z^5 + \dots)\\ &= \frac{1}{1 - z} + \frac{z}{1 - z} + z^3(1 + 2z + 2z^2 + 3z^3 + \dots)\\ &= \frac{1}{1 - z} + \frac{z}{1 - z} + z^3 G(z) \end{align*} So, \begin{align*} G(z)(1 - z^3) &= \frac{1}{1 - z} + \frac{z}{1 - z}\\ G(z)(1 - z^3) &= \frac{z + 1}{1 - z}\\ G(z) &= \frac{z + 1}{(1 - z)(1 - z^3)}\\ &= \frac{z + 1}{(1 - z)((1-z) (1+z+z^2))}\\ &= \frac{z + 1}{(1 - z)^2(z^2 + z + 1)}. \end{align*}

Answer 3

Without floors, ceilings, or rounding:

$\dfrac{2\sin(\frac23(n-1)\pi)}{3\sqrt3}+\dfrac{2n+1}3$

Answer 4

If you start counting at $1$, you have $f(n)=\lfloor \frac{n+1}3 \rfloor+\lfloor \frac {n+2}3 \rfloor$

Answer 5

OEIS gives several possibilities, depending on how the sequence continues.

One is $$\text{round}\left(\tan\left( \frac{\pi}{2} \left(1-\frac{1}{n}\right)\right)\right).$$