28
$\begingroup$

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?

$\endgroup$
6
  • 5
    $\begingroup$ $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$. $\endgroup$
    – Lord_Farin
    Jun 19, 2013 at 21:53
  • $\begingroup$ @Lord_Farin link on website please $\endgroup$
    – mnsh
    Jun 19, 2013 at 21:55
  • 2
    $\begingroup$ 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. $\endgroup$
    – Lord_Farin
    Jun 19, 2013 at 22:00
  • $\begingroup$ how the wolfram find the generating function of that sequence $\endgroup$
    – mnsh
    Jun 19, 2013 at 22:10
  • 2
    $\begingroup$ @hmedan.mnsh No need to explicitly say "thanks" on every answer, you can to so by upvoting the answers $\endgroup$ Jun 20, 2013 at 7:05

5 Answers 5

79
$\begingroup$

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

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

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

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

Without floors, ceilings, or rounding:

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

$\endgroup$
0
13
$\begingroup$

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

$\endgroup$
0
6
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ thanks alot for your answer $\endgroup$
    – mnsh
    Jun 19, 2013 at 22:44
  • 4
    $\begingroup$ -1 that sequence continues with 11,11, which is obviously not what OP was looking for... $\endgroup$ Jun 19, 2013 at 22:48
  • 10
    $\begingroup$ The OP was a little more polite. $\endgroup$
    – Henry
    Jun 19, 2013 at 23:40
  • 3
    $\begingroup$ 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. $\endgroup$
    – Jeff Burka
    Jun 20, 2013 at 2:29
  • 1
    $\begingroup$ @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... $\endgroup$
    – Jeyekomon
    Jun 20, 2013 at 18:30

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.