Daily Archives: February 3, 2018

A sequence I didn’t like

Standard

Following is a problem I encountered many times in my high school olympiads, but was never able to solve it. Hence didn’t like it.

What is the 100th term in the sequence 1,2,2,3,3,3,4,4,4,4,5,\ldots?

Following is a quick solution:

In this post, I will discuss the solution given in The Green Book of Mathematical Problems (problem 14).

Determine a function f(n) such that the n^{th} term of the sequence 1,2,2,3,3,3,4,4,4,4,5,\ldots is given by \lfloor f(n)\rfloor.

Let’s denote the n^{th} number of the sequence by a_n, i.e. a_n=\lfloor f(n)\rfloor. The integer m first occurs in the sequence when each of the integers from 1 to m-1 have already appeared 1 to m-1 times, respectively. Hence, if a_n=m then
n = [1 + 2 + 3 + \ldots + (m-1)]+1 +\ell = \frac{m(m-1)}{2} + 1 + \ell
for \ell = 0,1,2,\ldots, m-1.

Hence we have:
\displaystyle{0\leq n - \frac{m(m-1)}{2} - 1 \leq m-1}

\displaystyle{\Rightarrow \frac{m^2-m+2}{2}\leq n \leq \frac{m^2+m}{2}}

\displaystyle{\Rightarrow m^2-m+2\leq 2n \leq m^2+m}

\displaystyle{\Rightarrow \left(m-\frac{1}{2}\right)^2+\frac{7}{4}\leq 2n \leq \left(m+\frac{1}{2}\right)^2-\frac{1}{4}}

\displaystyle{\Rightarrow (2m-1)^2+7\leq 8n \leq (2m+1)^2 - 1}

\displaystyle{\Rightarrow (2m-1)^2 \leq 8n - 7 \leq (2m+1)^2 - 8}

\displaystyle{\Rightarrow (2m-1)^2 \leq 8n - 7 < (2m+1)^2}

\displaystyle{\Rightarrow 2m-1 \leq \sqrt{8n-7}<2m+1}

\displaystyle{\Rightarrow m \leq \frac{1+\sqrt{8n-7}}{2} < m+1}

\displaystyle{\Rightarrow m=\left\lfloor \frac{1+\sqrt{8n-7}}{2} \right\rfloor}

Hence we have a_n = \left\lfloor \frac{1+\sqrt{8n-7}}{2} \right\rfloor. Thus, we have

\displaystyle{\boxed{f(n) =\frac{1+\sqrt{8n-7}}{2}}}

Now compared to the earlier solution obtained by observing the pattern, one might ask “Is there is a better formula?”. For that, you might also look at the discussion at Math.SE.

Advertisements