# Given a sequence find nth term

Suppose a sequence is given -: 3, 8, 20, 43, 83, 148 ...

We can find the differences between consecutive terms and do that over and over again until we have same differences (as Pascal's triangle)

3   8   20  43  83  148
\ / \ / \ / \ / \ /
5  12   23  40  65
\ / \ / \ / \ /
7   11  17  25
\ / \ / \ /
4   6   8
\ / \ /
2   2


How to find 'n-th term' and 'sum of first n term' of these kind of sequences?

• If you have to take differences $d$ times to get a constant then you can fit a $d$ degree polynomial and you have enough information to set up $d+1$ simultaneous equations to find the coefficients. For the cumulative sum, obviously you need to take differences $d+1$ times to get the same constant and you can find the corresponding $d+1$ degree polynomial. This is an exercise in discrete calculus – Henry Nov 6 '16 at 14:28
• Have a look at this: citeseerx.ist.psu.edu/viewdoc/… – Olivier Oloa Nov 6 '16 at 14:45
• Check out part $(1)$ of my answer here math.stackexchange.com/questions/1878810/… as to why, if we assume all other first terms of the differences are $0$, and let $a_0$ represent the first term we have $a_n=3{n \choose 0}+5{n \choose 1}+7{n \choose 2}+4{n \choose 3}+2{n \choose 4}$. Notice the connection with the first terms of the sequences above. – Ahmed S. Attaalla Nov 6 '16 at 17:43
• For the sum, use the hockey stick identity. – Ahmed S. Attaalla Nov 6 '16 at 17:52

If we rotate the triangle $120^\circ$ (assuming the triangle is equilateral) clockwise, we have the following (original series shown in red; ignore items in blue and green for now):

$$\begin{array} &&&&&&&&\\ &\color{blue}{a_6}&&a_5 &&a_4 &&a_3 &&a_2&&a_1&&a_0\\ &\color{blue}\downarrow&&\downarrow&&\downarrow &&\downarrow&&\downarrow&&\downarrow&&\downarrow\\ &\color{blue} 0&&0 &&2 && 4 &&7 &&5 &&\color{red}3\\ &&\color{blue}0 &&2 &&6 &&11 &&12 &&\color{red}8 &\color{red}\uparrow\\ &&& \color{blue}2&&8 &&17 &&23 &&\color{red}{20}&\color{red}\uparrow&\color{red}{b_0}\\ &&&&\color{blue}{10}&&25 &&40 &&\color{red}{43}&\;\color{red}\uparrow&\color{red}{b_1}\\ &&&&&\color{blue}{35}&&65 &&\color{red}{83}&\;\color{red}\uparrow&\;\color{red}{b_2}\\ &&&&&&\color{blue}{100}&&\color{red}{148}&\;\color{red}\uparrow&\;\color{red}{b_3}\\ &&&&&&&\color{green}{248}&\;\color{red}\uparrow&\;\color{red}{b_4}\\ &&&&&&&\color{green}{\;\;\uparrow}&\;\color{red}{b_5}\\ &&&&&&&\color{green}{\;\;b_6} \end{array}$$

In this triangle, any number is the sum of the two numbers above it and immediately to the left and right, similar to Pascal's triangle. Hence we have

\begin{align} b_0&=\binom 00a_0\\ b_1&=\binom 10 a_1+\binom 11 a_0\\ b_2&=\binom 20a_0+\binom 21a_1+\binom 22a_2\\ &\vdots \\ b_n&=\sum_{r=0}^n \binom nr a_r \end{align}

Further, if the bottom row in the number triangle in the original question has elements of $2$ all the way, this means $a_r=0$ for $r\ge5$. We can then compute $b_n$ with only $a_0, a_1, a_2, a_3, a_4$, the values of which we already have.

Hence, the general formula for $b_n$ becomes $$\color{red}{b_n=\sum_{r=0}^{\min(4,n)} \binom nr a_r}\\ \color{red}{(a_r=3,5,7,4,2 \text{ for } r=0,1,2,3,4)}$$

This is also general formula for $n$-th term of the original series (the first term indexed as $n=0$).

Sum of first $n$ terms

The sum of the first $n$ terms is given by

\begin{align} \sum_{j=0}^{n-1}b_j &=\sum_{j=0}^{n-1}\sum_{r=0}^{\min (4,j)}\binom jr a_r\\ &=\sum_{r=0}^{\min(4,n-1)} \sum_{j=r}^{n-1}\binom jr a_r\\ &=\color{red}{\sum_{r=0}^{\min(4,n-1)} \binom n{r+1} a_r}\\ \end{align}

(see the solution here for an illustration)

Check

As a quick check, we compute $b_6$ by hand (shown in blue and green in the diagram) and arrive at $248$.

Using the formula, we have $$b_6=\binom 61 \cdot 3 +\binom 62\cdot 5+\binom 63\cdot 7+\binom 64\cdot 4+\binom 65\cdot 2=248$$ as well.

It is interesting to note that we can compute $a_n$ directly from $b_r (r=0,1,\cdots n)$, using $$a_n=\sum_{r=0}^n(-1)^{n+r}\binom nr b_r$$

For instance, $a_3=-1(3)+3(8)-3(20)+1(43)=4$.

This is because the inverse of a Pascal matrix (a left-aligned Pascal's triangle) is also a Pascal matrix, but with elements of alternating sign!
(Discovered this in the course of solving this problem!)

• Wow, wtf kind of trickery is this?! I give you an $\color{red}{\large\mathbf{A}\text{+}}$ – Simply Beautiful Art Nov 6 '16 at 17:55
• @SimpleArt - Thanks! Very kind of you :) – Hypergeometricx Nov 6 '16 at 17:59
• The result in your Additional Note is also a consequence of the Möbius inversion formula [PDF] on the poset of subsets of $[n]$. – Brian M. Scott Nov 6 '16 at 21:39
• @BrianM.Scott - Thanks for the reference. – Hypergeometricx Nov 7 '16 at 9:07

Well, the bottom row is given by

$$a_n=2$$

So that the row above it is given by

$$b_n=2(n+1)$$

And the row above

$$c_n=5+n(n+1)$$

And

$$d_n=5n+\frac{n(n^2-1)}3$$

So finally, we have

$$e_n=3+\frac{5n(n-1)}2+\frac{n(n^2-1)(n-2)}{12}$$

And the sum of the first $n$ terms would be given by the row above that,

$$f_n=3n+\frac{5n(n-1)(n-2)}6+\frac{n(n^2-1)(n-2)(n-3)}{60}$$

As to how I found those, I used the fact that

$$x_k(n+1)-x_k(n)=x_{k-1}(n)$$

where

$$x_k(n)=\frac{(n+1)(n+0)(n-1)\dots(n+1-k)}{k!}$$

which is basically how your triangle was constructed.

Also, the sum of each line is equal to the above line plus a constant.