2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Would someone please tell, how to derive it? $\endgroup$ – Mayank M. Aug 9 '16 at 16:30
  • 1
    $\begingroup$ Possible duplicates: math.stackexchange.com/q/877771/321264; math.stackexchange.com/q/455511/321264 $\endgroup$ – StubbornAtom Aug 9 '16 at 17:45
  • $\begingroup$ @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). $\endgroup$ – Mayank M. Aug 9 '16 at 17:52
  • $\begingroup$ The derivation has been shown, hasn't it? $\endgroup$ – StubbornAtom Aug 9 '16 at 17:55
4
$\begingroup$

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:

enter image description here

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 $$

$\endgroup$
4
$\begingroup$

$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$$

$\endgroup$
  • 1
    $\begingroup$ lol, did you find it in Putnam and Beyond? $\endgroup$ – Jorge Fernández Hidalgo Aug 9 '16 at 16:30
  • $\begingroup$ Would you please post the derivation too? $\endgroup$ – Mayank M. Aug 9 '16 at 16:33
  • 1
    $\begingroup$ I did addition! $\endgroup$ – Roman83 Aug 9 '16 at 16:38
  • $\begingroup$ 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? $\endgroup$ – Mayank M. Aug 9 '16 at 16:40
  • 1
    $\begingroup$ @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? $\endgroup$ – Roman83 Aug 9 '16 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.