Given a sequence find nth term

Question

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?

Answer 1

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.

---

Additional Note

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!)

Answer 2

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.