generalised formula for sum of first $n$ tetranacci numbers

Question

In the case of Fibonacci numbers, the formula for the sum of first $n$ numbers of the series is $f(n+2)-1$, but in the case of tetranacci numbers I am unable to arrive at such formula. Thanks.

Answer 1

Marcellus E. Waddill, The Tetranacci Sequence and Generalizations, gives the following identity:

$$\sum_{i=0}^n\mu_i=\frac13\Big(\mu_{n+2}+2\mu_n+\mu_{n-1}+2\mu_0+\mu_1-\mu_3\Big)\;,\tag{1}$$

where $\mu_0,\mu_1,\mu_2,\mu_3$ are arbitrary initial values and $\mu_n=\mu_{n-1}+\mu_{n-2}+\mu_{n-3}+\mu_{n-4}$ for $n\ge 4$; it is formula $(39)$ in the paper. It can be proved by induction, but Waddill gives a nicer proof by summing the identities $$\mu_k+\mu_{k+1}+\mu_{k+2}=\mu_{k+2}-\mu_{k+1}$$ for $k=0,\dots,n$ to obtain $$\sum_{k=0}^n\mu_k+\left(\sum_{k=0}^n\mu_k+\mu_{n+1}-\mu_0\right)+\left(\sum_{k=0}^n\mu_i+\mu_{n+1}+\mu_{n+2}-\mu_0-\mu_1\right)=\mu_{n+4}-\mu_3$$ and then $$3\sum_{k=0}^n\mu_k+2\mu_{n+1}+\mu_{n+2}-2\mu_0-\mu_1=\mu_{n+4}-\mu_3\;,$$ which can be rearranged to yield

$$\begin{align*} 3\sum_{k=0}^n\mu_k&=\mu_{n+4}-2\mu_{n+1}-\mu_{n+2}-\mu_3+2\mu_0+\mu_1\\ &=(\mu_{n+3}+\mu_{n+2}+\mu_{n+1}+\mu_n)-2\mu_{n+1}-\mu_{n+2}+2\mu_0+\mu_1-\mu_3\\ &=\mu_{n+3}-\mu_{n+1}+\mu_n+2\mu_0+\mu_1-\mu_3\\ &=(\mu_{n+2}+\mu_{n+1}+\mu_n+\mu_{n-1})-\mu_{n+1}+\mu_n+2\mu_0+\mu_1-\mu_3\\ &=\mu_{n+2}+2\mu_n+\mu_{n-1}+2\mu_0+\mu_1-\mu_3\;, \end{align*}$$

as desired. If you set $\mu_0=\mu_1=\mu_2=0$ and $\mu_3=1$, $(1)$ becomes

$$\sum_{i=0}^n\mu_i=\frac13\Big(\mu_{n+2}+2\mu_n+\mu_{n-1}-1\Big)\;.$$

Answer 2

This can also be solved by a matrix-ansatz (and then generalized in a completely obvious way).
Example: assume a vector A containing your first four values, say
$\qquad \small A=[1,3,4,5] $ .
Next consider the transfermatrix, say T which defines the composition of the next entry by $\small 1*1 + 3*1 + 4*1 + 5*1 =13$, and simply shifts the old entries $\small [1,3,4,5] \to [3,4,5,13] $ .
The required matrix T looks like

$\qquad \small T=\begin{bmatrix} 0&0&0&1\\1&0&0&1 \\0&1&0&1 \\0&0&1&1\\ \end{bmatrix} $

Then we have the iteration for the computation of consecutive elements of the tetranacci-sequence simply by
$\qquad \small A_{k+1} = A_k \cdot T $
or, even better:
$\qquad \small A_k = A \cdot T^k $

To sum the consecutive entries we can simply use the sum of the powers of T:
$\qquad \small S_k = A \cdot ( T^0 + T^1 + T^2 + ... + T^{k-1}) $
and the leading part of the geometric-series for the matrix T (also known as Neumann-series) is then
$\qquad \small U_k = (T^k - I) \cdot (T-I)^{-1} $ .
Thus the sum of the first k elements of the tetranacci-sequence can be found by

$\qquad \small S_k = A \cdot U_k $

and for k=5 I get

$\qquad \small S_k = [26, 50, 94, 180] $

where 26 (=1+3+4+5+13) is the sum of the first 5 elements of the sequence.

It is obvious, how this can be generalized in two ways:

• different starting values: either modify the (example) init-values in A (or keep them symbolic)
• different type of m-nacci-sequences: just increase the size of T in the obvious way

Answer 3

Denote the tetranacci numbers by $t(n)$. Then $$ \sum_{k=0}^n t(k) = \frac{t(n) - t(n+1) + t(n+3) - 1}{3}. $$ If you prefer your identity to involve $t(n+a),t(n+b),t(n+c),t(n+d)$ instead, just solve linear equations, not forgetting the constant term.

---

As commented above, since $t(n)$ is a linear combination of four powers $$ t(n) = c_1 \lambda_1^n + c_2 \lambda_2^n + c_3 \lambda_3^n + c_4 \lambda_4^n, $$ if we take sums then we get $$ \sum_{k=0}^n t(k) = \frac{c_1}{\lambda_1 - 1} \lambda_1^{n+1} + \cdots + \frac{c_4}{\lambda_4 - 1} \lambda_4^{n+1} - \left( \frac{c_1}{\lambda_1 - 1} + \cdots + \frac{c_4}{\lambda_4 - 1} \right). $$ If you put in $$ \sum_{k=0}^n = A t(n) + B t(n+1) + C t(n+2) + D t(n+2) + E $$ then you can solve a linear system to get the values of $A,B,C,D$: $$ \begin{align*} \frac{c_1}{\lambda_1 - 1} \lambda_1 &= A + B\lambda_1 + C\lambda_1^2 + D\lambda_1^3 \\ \cdots \\ \frac{c_4}{\lambda_4 - 1} \lambda_4 &= A + B\lambda_4 + C\lambda_4^2 + D\lambda_4^3 \end{align*} $$ The system must have a solution since the coefficients on the right-hand side form a Vandermonde matrix. The remaining coefficient $E$ can be read off directly: $$ E = - \left( \frac{c_1}{\lambda_1 - 1} + \cdots + \frac{c_4}{\lambda_4 - 1} \right). $$

Given that we know that such a representation exists, we can forget about $c_1,\ldots,c_4,\lambda_1,\ldots,\lambda_4$ and calculate the coefficients $A,B,C,D,E$ directly by solving a different system of equations: $$ \begin{align*} At(0) + Bt(1) + Ct(2) + Dt(3) + E &= t(0), \\ At(1) + Bt(2) + Ct(3) + Dt(4) + E &= t(0) + t(1), \\ \cdots \\ At(4) + Bt(5) + Ct(6) + Dt(7) + E &= t(0) + t(1) + t(2) + t(3) + t(4). \end{align*} $$ In order to find five unknowns we need five equations.