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

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?

• $G_n(a_n)(z)$ is the closed form for the power series $\sum_n a_n z^n$ with coefficients $a_n$; that is, $1+2z+2z^2+3z^3+4z^4+\ldots$. It is called the generating function for the $a_n$. Commented Jun 19, 2013 at 21:53
– mnsh
Commented Jun 19, 2013 at 21:55
• See Stahl's answer, which refers to Wikipedia. I'm not knowledgeable in the field so I can't help you past this point; sorry for that. Commented Jun 19, 2013 at 22:00
• how the wolfram find the generating function of that sequence
– mnsh
Commented Jun 19, 2013 at 22:10
• @hmedan.mnsh No need to explicitly say "thanks" on every answer, you can to so by upvoting the answers Commented Jun 20, 2013 at 7:05

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

• @ Did: very elegant! Or Floor[n - n^(2/3)], n= 4, 5, ... OEIS A135672 Commented Dec 11, 2014 at 14:23
• @Dr.WolfgangHintze Hmmm... I don't think so.
– Did
Commented Dec 11, 2014 at 23:43
• @ Did: you are right, it deviates starting from the 15th term. Commented Dec 12, 2014 at 14:10

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*}

• Although I said I didn't really know any books on the topic, I have heard some good things about generatingfunctionology, which is free online. You can find some nice examples of the uses of generating functions in there. Commented Jun 19, 2013 at 22:03
• how the wolfram find the generating function of that sequence
– mnsh
Commented Jun 19, 2013 at 22:16
• @hmedan.mnsh I've edited my answer to provide the derivation of the generating function. Commented Jun 19, 2013 at 22:33
• thanks alot =D =D =D =D =D =D
– mnsh
Commented Jun 19, 2013 at 22:40
• @hmedan.mnsh Concrete Mathematics has a one-chapter introduction to generating functions that is pretty good.
– MJD
Commented Jun 20, 2013 at 18:23

Without floors, ceilings, or rounding:

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

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

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

• -1 that sequence continues with 11,11, which is obviously not what OP was looking for... Commented Jun 19, 2013 at 22:48