4
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ – Henry Nov 6 '16 at 14:28
  • $\begingroup$ Have a look at this: citeseerx.ist.psu.edu/viewdoc/… $\endgroup$ – Olivier Oloa Nov 6 '16 at 14:45
  • 1
    $\begingroup$ 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. $\endgroup$ – Ahmed S. Attaalla Nov 6 '16 at 17:43
  • $\begingroup$ For the sum, use the hockey stick identity. $\endgroup$ – Ahmed S. Attaalla Nov 6 '16 at 17:52
5
$\begingroup$

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

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

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.

$\endgroup$

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.