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.
Best Answer
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 $$