How to find k term in a series.

I've a series in which the nth term repeats n times.
For example see this :
1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ...

So the question which I want to ask is that is there any way (like a formula) to get the kth term from the series (say 2000th term) except direct finding each and every term.
I also request to tell the derivation.
Note: This is not my HW question (although it may look like! ), I rather prefer doing them by myself.

• Would someone please tell, how to derive it? – Mayank M. Aug 9 '16 at 16:30
• Possible duplicates: math.stackexchange.com/q/877771/321264; math.stackexchange.com/q/455511/321264 – StubbornAtom Aug 9 '16 at 17:45
• @StubbornAtom the 1st link tried to verify the formula itself (means he/she knew it). The 2nd link asks the validity of the formula (again he knew it). But rather I asked how to get the formula, that is derivation (means I didn't knew it). – Mayank M. Aug 9 '16 at 17:52
• The derivation has been shown, hasn't it? – StubbornAtom Aug 9 '16 at 17:55

Rather than try directly find the number associated with a position in the sequence, let us instead first try to find the position in the sequence associated with a number. That will turn out to be easier, and we can then use that information as a kind of "bracket" to identify the number associated with a given position.

Specifically, how far do the $1$'s extend? Well, there's only one $1$, and it's in the first position.

How far do the $2$'s extend? There are two $2$'s, and they begin immediately after the $1$, so the last one is in the third ($1+2 = 3$) position.

How far do the $3$'s extend? There are three $3$'s, and they begin immediately after the $2$'s, so the last one is in the sixth ($1+2+3 = 6$) position.

Hopefully, you will now see the pattern. If you want to find the last number $n$, whatever $n$ happens to be, you will find it in the $1+2+3+\cdots+n$ position. Numbers of this form are called triangular numbers: In that article, you will also find a formula for computing the $n$th triangular number directly, rather than summing up the first $n$ integers:

$$T_n = \frac{n(n+1)}{2}$$

This formula is key to the process of finding the number at a given position. We can say, for instance, that the number at a given position $k$ is $4$ if $k$ is in the fourth row of the triangle—that is, if we write the series $a_1, a_2, a_3, \ldots$, then $a_k = 4$ if and only if

$$T_3 < k \leq T_4$$

That is, the number cannot be in the first three rows (the triangle represented by $T_3$), and it must be in the first fourth rows (the triangle represented by $T_4$). Ergo, it must be in the fourth row.

In much the same way, in general, $a_k = n$ if and only if

$$T_{n-1} < k \leq T_n$$

Using our formula above, we have

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

This gives us a condition on $k$ in terms of $n$; we want to flip that around to give a condition on $n$ in terms of $k$. That way, we will have a formula that will return the value of $n = a_k$. First multiply through by $2$:

$$(n-1)n < 2k \leq n(n+1)$$

$$n^2-n < 2k \leq n^2+n$$

We do something called "completing the square": We add something to the first and last expressions in order to put them in the form of a perfect square. (Of course, we'll have to add the same thing to the middle expression as well).

$$n^2-n+\frac{1}{4} < 2k+\frac{1}{4} \leq n^2+n+\frac{1}{4}$$

Because we've completed the square, we can write this as

$$\left(n-\frac{1}{2}\right)^2 < 2k+\frac{1}{4} \leq \left(n+\frac{1}{2}\right)^2$$

We then take the square root of all sides:

$$n-\frac{1}{2} < \sqrt{2k+\frac{1}{4}} \leq n+\frac{1}{2}$$

We subtract $1/2$ from all sides to obtain

$$n-1 < \sqrt{2k+\frac{1}{4}}-\frac{1}{2} \leq n$$

In other words, $n$ must be the smallest integer greater than or equal to the middle expression. This can be written more succinctly as

$$n = \left\lceil \sqrt{2k+\frac{1}{4}}-\frac{1}{2} \right\rceil$$

$m-$th term of the sequence is equal to $n$ if and only if the inequality: $$1+2+...+(n-1)+1\le m \le 1+2+...+(n-1)+n \Leftrightarrow$$ $$\Leftrightarrow \frac{(n-1)n}{2}+1\le m\le\frac{n(n+1)}{2} \Leftrightarrow$$ $$\Leftrightarrow n^2-n+2 \le 2m \le n^2+n \Leftrightarrow$$ $$\Leftrightarrow n^2- n+\frac14< m < n^2+n+\frac14 \Leftrightarrow$$ $$\Leftrightarrow n-\frac12 < \sqrt{2m} < n+\frac12 \Leftrightarrow$$ $$\Leftrightarrow n<\sqrt{2m}+\frac12<n+1$$ $$n=\lfloor\sqrt{2m}+\frac12 \rfloor$$

Answer: $$a_m=\lfloor\sqrt{2m}+\frac12 \rfloor, m\ge 1$$

• lol, did you find it in Putnam and Beyond? – Jorge Fernández Hidalgo Aug 9 '16 at 16:30
• Would you please post the derivation too? – Mayank M. Aug 9 '16 at 16:33
• I did addition! – Roman83 Aug 9 '16 at 16:38
• Well, I'm really sorry to ask you again but I'm not a math expert but a normal 10th grade student. Would you please explain the proof? – Mayank M. Aug 9 '16 at 16:40
• @MayankM. $m-$th term of the sequence is equal to $n$ if and only if the inequality: $$1+2+...+(n-1)+1\le m \le 1+2+...+(n-1)+n$$ It's clear? – Roman83 Aug 9 '16 at 16:43