# 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$. –  Lord_Farin Jun 19 '13 at 21:53
@Lord_Farin link on website please –  mhd.math Jun 19 '13 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. –  Lord_Farin Jun 19 '13 at 22:00
how the wolfram find the generating function of that sequence –  mhd.math Jun 19 '13 at 22:10
@hmedan.mnsh No need to explicitly say "thanks" on every answer, you can to so by upvoting the answers –  Tobias Kienzler Jun 20 '13 at 7:05

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. –  Stahl Jun 19 '13 at 22:03
how the wolfram find the generating function of that sequence –  mhd.math Jun 19 '13 at 22:16
@hmedan.mnsh I've edited my answer to provide the derivation of the generating function. –  Stahl Jun 19 '13 at 22:33
thanks alot =D =D =D =D =D =D –  mhd.math Jun 19 '13 at 22:40
@hmedan.mnsh Concrete Mathematics has a one-chapter introduction to generating functions that is pretty good. –  MJD Jun 20 '13 at 18:23

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

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

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

-
thanks alot for your answer –  mhd.math Jun 19 '13 at 22:44
-1 that sequence continues with 11,11, which is obviously not what OP was looking for... –  BlueRaja - Danny Pflughoeft Jun 19 '13 at 22:48
The OP was a little more polite. –  Henry Jun 19 '13 at 23:40
I don't think OEIS is really a very well-known resource. Just googling the sequence will not bring you there, and even if you search something like "number sequence", OEIS is pretty far down. –  Jeff Burka Jun 20 '13 at 2:29
@JeffreyBurka Fun fact: OEIS takes first place (it beats the wikipedia!) when searching for "integer sequences". In the "number sequences" it takes 15th place which, indeed, isn't the best position... –  Jeyekomon Jun 20 '13 at 18:30