The Anomalous Closed Form of 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ..

Sorry for being out for so long! Anyhow, let’s just jump right in. I want to dedicate this post to a very special sequence.

Problem:
Find the closed form (that is, a formula for determining the nth term) of the sequence 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, \dots, where each integer m repeats m times.

Motivation for Writing Post:
This sequence has a bit of history with me which I want to quickly gloss over, although feel free to skim/skip this of course:

I had first encountered this sequence my junior year of high school online (Twitter, I believe, during the whole two weeks I used Twitter). I had followed someone who posted math problems everyday and one day he posted: “Find the formula for the nth term of 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, …” It immediately caught my eye and I started to attempt it… and got nowhere after working for a good hour or so straight. I left it for a bit to clear my mind then came back and suddenly had an epiphany and saw the pattern hidden in plain sight — and from there it was straight forward!

Two years later in my freshman year of college I was in a Discrete Structures course covering sequences and series and my professor had written up multiple different lists of elements on the board asking students to find the closed form of each sequence. Lo and behold, there it was! Of course, I couldn’t remember the formula off the top of my head and I recalled it taking a good few minutes to find the answer, so I just left that blank (this wasn’t an assignment, just the professor sort of testing us mid-lecture). Afterwards, he went through each sequence and showed us its closed form, and when he got to the infamous 1, 2, 2, 3, 3, 3, … he asked around if anyone found its formula and no one responded and I just smiled at him (I thought he must be playing off of how surely no one calculated it in time). To my surprised, he then went and said “You actually can’t find the formula for this one because it doesn’t exist! All you can say is each integer m repeats m times.” This really bothered me, and I actually approached him at the end of class telling him that such a formula exists and showed him the pattern embedded in the sequence — then that very night over email I discussed the actual derivation of the closed form with him. 🙂

Besides this though, I’ve met a good handful of people who didn’t believe me when I said this sequence has a closed form. I’ve always wanted to write this just to show where the pattern in this series is and how to use to your advantage.

Solution:
Let’s begin by writing out the sequence a bit so we can closely examine it.
a_1 = 1
a_2 = 2
a_3 = 2
a_4 = 3
a_5 = 3
a_6 = 3
a_7 = 4
a_8 = 4
a_9 = 4
a_{10} = 4
a_{11} = 5
Something seems to be going on with the subscripts of a_n… Look where terms stop repeating, 1 stops at 1, 2 at 3, 3 at 6… Putting where they stop in sort of their own little sequence b_n, we have 1, 3, 6, 10, \dots. Maybe you’ve encountered this before — b_n is actually a sequence of what’s known as triangular numbers! That is, you get each number by summing up natural numbers, like this:
b_1 = 1 = 1
b_2 = 3 = 1 + 2
b_3 = 6 = 1 + 2 + 3
b_4 = 10 = 1 + 2 + 3 + 4
b_5 = 15 = 1 + 2 + 3 + 4 + 5
\dots
\displaystyle{b_n = 1 + 2 + 3 + \dots + (n-1) + n =  \sum_{r=1}^n r = \frac{n^2+n}{2}}

There’s our hidden pattern, exactly what we needed. Giving us the following:

Lemma:
If a_n=k, then we have

\displaystyle{ \frac{(k-1)^2+(k-1)}{2} < n \leq \frac{k^2+k}{2}    }

Proof: Since m repeats m times and we start with a_1 = 1, we then have a_{1+2} = 2 as the final term of 2, a_{1+2+3}=3 as the final term of 3, and in general a_{ \frac{n^2+n}{2}}=n as the final term of n. This justifies that if a_n=k then n \leq \frac{k^2+k}{2}. For the other side of the inequality, note that if a_n=k then k-1 stopped repeating at \frac{(k-1)^2+(k-1)}{2}, so beginning after this term is where k begins repetition. This concludes the proof.

It practically follows as corollary what we do next. Using the inequality from our lemma, we now just proceed with some algebraic manipulation:
\displaystyle{ \frac{(k-1)^2+(k-1)}{2} < n \leq \frac{k^2+k}{2}    }
\displaystyle{ (k-1)^2+(k-1) < 2n \leq k^2+k    }
\displaystyle{ (k-1)^2+(k-1)+\frac{1}{4} < 2n+\frac{1}{4} \leq k^2+k+\frac{1}{4}    }
Note, the \frac{1}{4} is added in order to factor in the next step.
\displaystyle{ \left[ (k-1)+\frac{1}{2}\right]^2 < 2n+\frac{1}{4} \leq \left( k+\frac{1}{2} \right) ^2   }
\displaystyle{ (k-1)+\frac{1}{2} < \sqrt{2n+\frac{1}{4}} \leq k+\frac{1}{2}   }
\displaystyle{ k-1 < \sqrt{2n+\frac{1}{4}}-\frac{1}{2} \leq k  }
Lastly, we’re going to take the ceiling function of everything, giving
\displaystyle{ \lceil \sqrt{2n+\frac{1}{4}}-\frac{1}{2} \rceil = k  }
providing us our final answer of…

The sequence 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, \dots, where m repeats m times, has the closed form

a_n = \lceil \sqrt{2n+\frac{1}{4}}-\frac{1}{2} \rceil .

The ceiling function (\lceil x \rceil means always round up x to the nearest integer) was added because \sqrt{2n+\frac{1}{4}}-\frac{1}{2} was between the two integers k-1 and k, and it is capable of only being an integer and is undefined for k-1, so it must be rounded up to k.

This wasn’t necessarily a one-glance proof and it may require some rereading to really understand the gist of everything, so please do reread it (I mean for goodness sake, it took me hours the first time to get this, and now I’m just throwing it all at you at once).

This problem always makes me think back to a quote I heard in a Numberphile video many months ago that managed to always stick with me, and I hope, perhaps after seeing this post, that it’ll stick with you as well.

“If you know something, prove it! Make sure you really understand that one thing and that often unlocks the rest.” — Daniel Erman, The Josephus Problem

Advertisements

6 thoughts on “The Anomalous Closed Form of 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ..

    • I’m glad you like the post! Alas, I don’t know of any books and after some searching around, the best I could find was Knopp’s “Theory and Application of Infinite Series” which gives the sequences a (somewhat daunting…) rigorous treatment. I don’t have any particular recommendations though, apologies!

      Like

  1. Just read in Stephen wolfram’s book you can also get this sequence with this recursive rule
    f(n) = 1+f(n-f(n-1)) where f(1) = 1
    just thought this was kind of interesting.

    Liked by 1 person

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s