What is the formula for finding the summation of the sequence : $1,2,5,12,26,51,...$ upto $n$ terms?

Question

Q)What is the formula for finding the summation of the sequence $1,2,5,12,26,51,...$ upto $n$ terms ?

I know how to find the summation of sequences like $1,2,3,...,$ upto $n$ terms ; $1,2,4,8,...,$ upto $n$ terms, $1,2,4,7,11,...$, upto $n$ terms.

Mainly what I am trying to say is that I know how to find the summations of an Arithmetic Progression, Geometric Progression, Arithmetico-Geometrico Progression.

The formula for finding the summation of a finite A.P. is $\frac{n}{2}[2a+(n-1)d]$; where $a$ is the $1^{st}$ term of the A.P., $d$ is the Common Difference of the A.P. and $n$ is the no. of terms of the A.P.

The formula for finding the summation of a finite G.P. is $a(\frac{r^{n}-1}{r-1})$ when $|r|$ is $> 1$ and $a(\frac{1-r^{n}}{1-r})$ when $|r|< 1 $ ; where $a$ is the $1^{st}$ term of the G.P., $r$ is the common ratio of the G.P., and $n$ is the no. of terms of the G.P.

Similarly I also know how to find the summation of an Arithmetico-Geometrico Progression.

But I don't know how to find the summation of a Progression where the terms of the difference of the difference of the difference will be in Arithmetic Progression.

In my question if I take the difference of the terms and make a sequence with these terms then the sequence will be {$1,3,7,14,...$ upto $n$ terms}. Again the sequence of the difference of these terms will be {$2,4,7,11,...$ upto $n$ terms}. Finally again the sequence of the difference of these terms will be {$2,3,4,5,...,$ upto $n$ terms}, which is in Arithmetic Progression.

But I can't understand how to further proceed. Please help me out.

Answer 1

The sum is $$S_n=\frac{1}{120}n(n^4+15n^2+104).$$ You just write the $n$th difference sequence and sum them up level by level. Explicitly: $$\{a_n\}=1,2,5,12,26,51,\cdots$$ $$\{b_n\}=1,3,7,14,25,\cdots$$ $$\{c_n\}=2,4,7,11,\cdots$$ $$\{d_n\}=2,3,4,\cdots=\{n+1\}.$$ Then $$c_n=c_1+\sum_{k=1}^{n-1}d_k=\frac{n^2+n+2}{2};$$ $$b_n=b_1+\sum_{k=1}^{n-1}c_k=\frac{n^3+5n}{6};$$ $$a_n=a_1+\sum_{k=1}^{n-1}b_k=\frac{n^4-2n^3+11n^2-10n+24}{24};$$ then finally $$S_n=\sum_{k=1}^na_n.$$

Answer 2

This can efficiently be done using generating functions.

Summing the coefficient sequence corresponds to multiplying the generating function by $\frac1{1-x}=\sum_{k=0}^\infty x^k$. There are some complications because you’re not including the first term as the first difference, but that can be accounted for by some modifications:

\begin{eqnarray*} \frac1{1-x}&=&1+x+x^2+x^3+\cdots\;,\\ \frac1{(1-x)^2}&=&1+2x+3x^2+4x^3+\cdots\;,\\ \frac1{(1-x)^2}+1&=&2+2x+3x^2+4x^3+\cdots\;,\\ \left(\frac1{(1-x)^2}+1\right)\frac1{1-x}&=&2+4x+7x^2+11x^3+\cdots\;,\\ \left(\left(\frac1{(1-x)^2}+1\right)\frac x{1-x}+1\right)\frac1{1-x}&=&1+3x+7x^2+14x^3+\cdots\;,\\ \left(\left(\left(\frac1{(1-x)^2}+1\right)\frac x{1-x}+1\right)\frac x{1-x}+1\right)\frac1{1-x}&=&1+2x+5x^2+12x^3+\cdots\;.\\ \left(\left(\left(\frac1{(1-x)^2}+1\right)\frac x{1-x}+1\right)\frac x{1-x}+1\right)\frac x{(1-x)^2}&=&x+3x^2+8x^3+20x^4+\cdots\;.\\ \end{eqnarray*}

Multiplying out and performing a partial fraction expansion yields (Wolfram|Alpha computation)

$$ x\left(\frac1{(1-x)^2}-\frac1{(1-x)^3}+\frac2{(1-x)^4}-\frac2{(1-x)^5}+\frac1{(1-x)^6}\right)\;. $$

Then extracting coefficients using $\left[x^n\right]\frac1{(1-x)^{k+1}}=\binom{n+k}k$ leads to (Wolfram|Alpha computation)

$$ \left[x^n\right]\left(x\left(\frac1{(1-x)^2}-\frac1{(1-x)^3}+\frac2{(1-x)^4}-\frac2{(1-x)^5}+\frac1{(1-x)^6}\right)\right)\\ =\left[x^{n-1}\right]\left(\frac1{(1-x)^2}-\frac1{(1-x)^3}+\frac2{(1-x)^4}-\frac2{(1-x)^5}+\frac1{(1-x)^6}\right)\\ =\binom n1-\binom{n+1}2+2\binom{n+2}3-2\binom{n+3}4+\binom{n+4}5\\ =\frac{n^5+15n^3+104n}{120}\;, $$

in agreement with Shujian’s answer.