Let $a_n$ be the $nth$ term of the sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, \dots$

Question

Question:
Let $a_n$ be the $nth$ term of the sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6\dots$, constructed by including the integer $k$ exactly $k$ times. Show that $a_n = \lfloor \sqrt{2n} + \dfrac{1}{2}\rfloor$.

Attempt:
Try to prove $k = a_n=\lfloor \sqrt{2n} + \dfrac{1}{2}\rfloor$ then $k = a_{n+k-1}=\lfloor \sqrt{2(n+k-1)} + \dfrac{1}{2}\rfloor$.

The inequality of $k = a_n=\lfloor \sqrt{2n} + \dfrac{1}{2}\rfloor$, is the following,

$$k \leq \sqrt{2n} + \dfrac{1}{2} < k + 1$$ $$k-\dfrac{1}{2} \leq \sqrt{2n} < k + \dfrac{1}{2}$$ $$\Big( k-\dfrac{1}{2} \Big)^2 \leq 2n < \Big(k +\dfrac{1}{2}\Big)^2$$ $$\dfrac{1}{2}\Big( k-\dfrac{1}{2} \Big)^2 \leq n < \dfrac{1}{2}\Big(k +\dfrac{1}{2}\Big)^2$$ $$\dfrac{1}{2}\Big( k-\dfrac{1}{2} \Big)^2 + k - 1 \leq n + k -1 < \dfrac{1}{2}\Big(k +\dfrac{1}{2}\Big)^2 + k - 1$$ $$\Big( k-\dfrac{1}{2} \Big)^2 + 2k - 2 \leq 2(n + k -1) < \Big(k +\dfrac{1}{2}\Big)^2 + 2k - 2$$ $$k^2 - k + \dfrac{1}{4} + 2k - 2 \leq 2(n+k - 1) < k^2 + k + \dfrac{1}{4} + 2k - 2$$ $$k^2 + k + \dfrac{1}{4} - 2 \leq 2(n+k - 1) < k^2 + 3k + \dfrac{9}{4} - \dfrac{9}{4} + \dfrac{1}{4} - 2$$ $$\Big( k+\dfrac{1}{2} \Big)^2 - 2 \leq 2(n+k - 1) < \Big( k+\dfrac{3}{2} \Big)^2 - 4$$

From here $2(n+k - 1) < \Big( k+\dfrac{3}{2} \Big)^2 - 4 \implies 2(n+k - 1) < \Big( k+\dfrac{3}{2} \Big)^2$ so I can take the square root of both sides. The problem is the left hand side, $\Big( k+\dfrac{1}{2} \Big)^2 - 2 \leq 2(n+k - 1)$ does not imply $\Big( k+\dfrac{1}{2} \Big)^2 \nleq 2(n+k - 1)$, thus we can't really get rid of the square.

It is easy to see that if we have $k = a_{n+k}=\lfloor \sqrt{2(n+k)} + \dfrac{1}{2}\rfloor$, the problems we encountered are avoided, but $k \neq a_{n+k}$.

Answer 1

Consider the following:

$k=1 \rightarrow 1$

$k=2 \rightarrow 2, 2$

$k=3 \rightarrow 3, 3, 3$

$k=4 \rightarrow 4, 4, 4, 4$

So for $k$th row, we get $a_n=k, n=\frac{(k-1)k}{2}+1, \frac{(k-1)k}{2}+2,\cdots,\frac{(k+1)k}{2}$.

Now we want to evaluate $a_n$, that is to find $k$ satisfying $\frac{(k-1)k}{2}<n\leq \frac{(k+1)k}{2}$,

so $k-\frac{1}{2}<\sqrt{(k-1)k}<\sqrt{2n}\leq \sqrt{k(k+1)}<k+\frac{1}{2} \Longrightarrow \sqrt{2n}-\frac{1}{2}<k<\sqrt{2n}+\frac{1}{2}$

then we get $k=[\sqrt{2n}+\frac{1}{2}] $ and $a_n=k$.

Answer 2

Hint1 :

For every $n$,there is a $m$ such that $\frac{m(m+1)}{2} \leq n < \frac{(m+1)(m+2)}{2}$.

Then $a_n = m$.

Hint 2:

For what values of $n$ you does the next equality hold?

$$\lfloor \sqrt{2n} + \dfrac{1}{2}\rfloor +1 = \lfloor \sqrt{2(n+1)} + \dfrac{1}{2}\rfloor$$

Answer 3

I am trying this question in a different way. As is evident from series interger 1 occurs first time at 1 st position integer 2 occurs first time after first term (1 + 0) integer 3 occurs for the first time after (0 +1 + 2 ) terms integer 4 occurs after (0 + 1 + 2 + 3 ) terms

so integer k will be present after (k(k-1)/2) terms, which means at [k(k-1)/2 + 1]th position

so if [k(k + 1)/2 + 1]th term is k then for nth term n=k(k+1)/2 + 1. Just express k in terms of n.

I did not try it so i don't know if this is correct

Answer 4

Let $t = \lfloor \sqrt{2n} + \dfrac{1}{2}\rfloor.$ By a look at the sequence $a_n,$ the $n$ for which $a_n=k$ satisfy $$k(k-1)/2+1 \le n < (k+1)k/2+1.\tag{1}$$ Now from the definition of $t$ we have $t \le \sqrt{2n}+1/2 < t+1$, from which after some manipulation we have $$8\frac{t(t-1)}{2}+1 \le 8n < 8 \frac{t(t+1)}{2}+1.$$ This can now be divided by $8$, and the $1/8$ on the left side coming from division of $1$ by $8$ may be rounded up to $1$ since $n$ is an integer. (The $1/8$ on the right side may be rounded up to $1$ since that only increases the right side to an integer.)

This then gives $$t(t-1)/2+1 \le n <t(t+1)/2+1,$$ showing that the $t$ defined via the floor function does the same job as the $k$ in the inequality $(1).$