What is intuition behind writing the explicit formula for a sequence?

Question

I am working through some sequence problems and am a bit stuck.

We are told to write the explicit formula for two sequences and then find $a_{100}$ and $a_{20}$ respectively. The two sequences are the following:

$S_1 = \{1, 3, 6, 10, 15, 21,...\}$

$S_2 = \{0, 3, 8, 15, 24,...\}$

These are both two famous sequence problems (the first being the pyramid problem).

What I have done is found the difference between each of the terms in the sequence with the preceding term. We then get for $S_1$:

$a_1 \ | \ a_2 \ | \ a_3 \ | \ a_4 \ | \ a_5...$

$1 \ \ |\ \ 3 \ \ |\ 6 \ \ |\ 10 \ \ |\ 15 \ |\ 21...$

$\ \ \ |+2|+3|+4|+5|+6...$

It is clear here that we are adding n to the preceding term. The recursive formula then goes as the following: $a_n = a_{n-1} + n$

For the explicit formula however I am a bit stuck.

The book solution explains that we take: $$a_n = 1 + 2 + 3 + \ ... \ + (n-2) + (n-1) + n$$

write it as:

$$a_n = n + (n-1) + (n-2) + \ ... \ + 3 + 2 + 1$$

and then add these two equations together to eventually derive $a_n = {1 \over 2}n(n+1)$

Here I am completely stuck. How did we get these two original equations, why did we add them, and how did we know how to do this? Is this just a derivation of a common formula that we are expected to know/memorize? If I had never seen this problem before what would have been the intuition here/way to find this solution?

For the second problem, I am a bit clearer on the sequence:

We are given:

$S_2 = \{0, 3, 8, 15, 24,...\}$ and clearly this is one less than the square of $n$ for each number resulting in an explicit formula of $a_n = n^2 - 1$. My only concern is that say you did not immediately notice that the was one less than the square of each number, how would you have derived this value? Again, are you just expected to know this and memorize it?

I am struggling a little bit with the intuition here. To me, it seems like these are just two examples that are expected to be memorized.

If anyone could provide any help, suggestions, links to resources, or intuition to solving either of these two problems that would be greatly appreciated. Thanks.

Answer 1

Your concerns about "how would I know to do this in order to derive that?" are completely legitimate, and unfortunately in general there is no systematic way to find an explicit formula for the $n$-th term $a_n$ of a sequence given only a recursive formula for the sequence. It's not like an algebra question where $2x+1=3$ and you can easily figure out that $x=1$, as you advance more and more in math, you'll find that these kinds of systematic methods largely do not exist (or maybe have not been discovered?), and you really have no choice but to rely on your intuition and observational skills. But trust me, as you get more and more exposure, it will become easier and more natural the farther you go :)

Answer 2

For the first one, as you noticed, you can write $a_n = a_{n-1} + n$. Now let's just do a summation from 1 to m on both sides:

$\sum_{n=1}^m a_n = \sum_{n=1}^m a_{n-1} + \sum_{n=1}^m n$

The left side can be expanded out as: $(a_1 + a_2 + \ldots + a_{m-1}) + a_{m}$.

The first term on the right side can be expanded out as: $a_0 + a_1 + a_2 + \ldots + a_{m-1}$, which is the same as the term in the brackets on the left side if we set $a_0=0$ (this is OK because the series starts at $n=1$).

So now we have:

$(a_1 + a_2 + \ldots + a_{m-1}) + a_{m} = a_0 + a_1 + a_2 + \ldots + a_{m-1} + \sum_{n=1}^m n$

Canceling out the common terms:

$a_m = \sum_{n=1}^m n = n(n+1)/2$. The last step can be derived from first principles (sum of an arithmetic progression) or you can just rely on a well established result.

Another way to approach this is to start again with $a_n = a_{n-1} + n$. Assuming $a_0=0$ as discussed above,

$a_1 = 1$

$a_2 = a_1 + 2 = 1 +2$

$a_3 = a_2 + 3 = 1 + 2 + 3$

Now you can see a pattern here: $a_n = 1 + 2 + 3 + \ldots + n$. You can reverse the terms in the summation and write the same equation as $a_n = n + (n-1) + (n-2) + \ldots + 1$.

If you add these equations, you get:

$2a_n = (1+n) + (2 + n - 1) + (3 + n - 2) + \ldots + (n + 1)$, i.e. $(n+1)$ added up $n$ times, which is $n(n+1)$. So $a_n$ is simply $n(n+1)/2$.

This proof (i.e. the one in your textbook) relies on a bit of jugglery whereas the first proof I gave is longer but I think easier to follow. You pick!

Answer 3

In general, finding explicit formulae for sequences is a combination of luck, experience, intuition, application of some known facts about sequences and a lot of work. Often, there is no predefined path to the solution. And there are also sequences which do not have an explicit formula, like the partial sums of the harmonic series.

However, if the explicit formula of a sequence is a polynomial, then this can easily be identified. If the explicit formula of the sequence of differences is a polynomial of degree $d,$ then the explicit formula of the sequence itself is a polynomial of maximum degree $d+1.$

Taking the second sequence as an example: The sequence of differences is $3,5,7,9,\ldots.$ If you fail to see the pattern in this sequence, you can try to form the sequence of differences of the sequence of differences: $2,2,2,\ldots$ This can be described by means of an polynomial of degree $0$ (a constant). Therefore $3,5,7,9,\ldots$ can be described by means of a polynomial of degree $1,$ which in turn means that $0,3,8,15,24,\ldots$ can be described by means of a polynomial of degree $2.$

If you want to find this polynomial systematically, you can interpolate the first elements of the sequence. For a polynomial of degree $d,$ you need the first $d+1$ elements of the sequence for that.

In the second example, you know that $a_n=c_2n^2+c_1n+c_0$ and $a_1=0$, $a_2=3$ and $a_3=8$. You can find $c_0,$ $c_1$ and $c_2$ by solving the system of linear equations \begin{eqnarray} 1^2\cdot c_2 + 1 \cdot c_1 +c_0 & = & 0 \\ 2^2\cdot c_2 + 2 \cdot c_1 +c_0 & = & 3 \\ 3^2\cdot c_2 + 3 \cdot c_1 +c_0 & = & 8 \\ \end{eqnarray} and you will get $c_0=-1$, $c_1=0$, $c_2=1$ and hence $a_n=n^2-1.$

This is more work than the solution shown in the text book, but it is something you can do systematically.

Answer 4

Here's a systematic way to get explicit formulas for polynomial sequences, and it builds on your idea to take differences. Instead of taking just one difference, construct a difference table by taking differences of the previous row, until you get a row of zeroes: \begin{matrix} \color{red}{1} &3 &6 &10 &15 &21 \\ \color{blue}{2} &3 &4 &5 &6 \\ \color{orange}{1} &1 &1 &1 \\ 0 &0 &0 \\ \end{matrix} Now read off the leftmost term in each row, yielding: $$\color{red}{1}\binom{n}{0}+\color{blue}{2}\binom{n}{1}+\color{orange}{1}\binom{n}{2}=1+2n+\frac{n(n-1)}{2}=\frac{n^2+3n+2}{2}.$$ But this formula assumes you started with $n=0$. Because you started with $n=1$, shift by $1$ unit to obtain $$a_n = \frac{(n-1)^2+3(n-1)+2}{2} = \frac{n(n+1)}{2}.$$

For your second example, the difference table is: \begin{matrix} \color{red}{0} &3 &8 &15 &24 \\ \color{blue}{3} &5 &7 &9 \\ \color{orange}{2} &2 &2 \\ 0 &0 \\ \end{matrix} Now read off the leftmost term in each row, yielding: $$\color{red}{0}\binom{n}{0}+\color{blue}{3}\binom{n}{1}+\color{orange}{2}\binom{n}{2}=0+3n+2\frac{n(n-1)}{2}=n^2+2n.$$ But this formula assumes you started with $n=0$, so shift by $1$ unit to obtain $$a_n = (n-1)^2+2(n-1) = n^2-1.$$