# 1,3,7,13,21,31 what come next?

It supposed to be some thing simple, but some how I don't get it.

I have a function with constant rate increase of 2. How can I calculate the n'th number?

It starts with 1, and it looks like this:

$$1,3,7,13,21,31,43...$$

• Hint: Find first and second differences. – randomgirl Feb 3 '15 at 3:20
• Do you know this pattern represents the no. of regions formed by the intersection of n circles? link – Max Payne Feb 15 '16 at 15:46

$f(n)=n^2$ goes $1,4,9,16,25,36,49$, it has the correct rate increase but the increase starts too fast.

$f(n)=n^2-n$ goes $0,2,6,12,20,30,42$ has the correct rate increase and initial increase. but it starts too small.

$f(n)=n^2-n+1$ fits perfectly.

• Basically: You can first select the coefficient of $n^2$ to get the correct rate increase, then select the coefficient of $n$ to get the correct initial rate and then select the constant term to get the correct initial value. – Jorge Fernández Hidalgo Feb 3 '15 at 3:23
• @ModdedBear I think you meant $n^2 - n + 1$ unless you meant to skip the first term :) – benji Feb 3 '15 at 3:28
• @induktio looking forward to your answer. – Jorge Fernández Hidalgo Feb 3 '15 at 3:31
• @ModdedBear I liked your answer in its own right, but I was thinking of something more along the lines of recurrence relations and induction. – Daniel W. Farlow Feb 3 '15 at 3:36
• It should be mentioned that this question was asked in chat (and received an answer) several minutes before he posted the question. It seems the op left out the information that the sequence described starts with the $0^{th}$ term, $f(0)=1,f(1)=3,\dots$. This answer assumes it starts on the $1^{st}$ term with $f(1)=1,f(2)=3,\dots$. To change from one to the other, it is just a difference of adding $2n$ to make it $n^2+n+1 = 1+2T(n)$. Useful method either way. – JMoravitz Feb 3 '15 at 3:51

First observe that the second differences are constant.

Then we can assume it is $$f(x) = ax^2 + bx + c.$$

Subbing in $x = 0,1,2$ we have the system of equations

$$\pmatrix{1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 3 \\ 1 & 2 & 4 & 7} = \pmatrix{1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 2 \\ 0 & 2 & 4 & 6} = \pmatrix{1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 2 & 2} = \pmatrix{1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1}.$$

Thus, we have $f(x) = x^2 + x + 1$.

If $$a = 1 + 2 + \ldots + n,$$ then it is also true that $$2a = (1 + 2 + \ldots + n) + (n + (n - 1) + \ldots + 1) = (n + 1) + \ldots (n + 1) = n(n +1).$$
$$1 + 2 + \ldots + n = \frac{n(n+1)}{2}.$$
Finally, if $T(0) = 1$, then your sequence is just
$$T(n) = T(0) + 2 + 4 + \ldots + 2n = 1 + 2(1 + 2 + \ldots + n) = 1 + 2\frac{n(n+1)}{2} = n^2 + n + 1.$$