generalised formula for sum of first $n$ tetranacci numbers 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.
 A: 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)\;.$$
A: 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

A: 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.
