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.

-
One can express the $n$-th whatever-nicci number as a linear combination of the $n$-th powers of the roots of a certain polynomial. Then the sum is just that linear combination of the sum of finite geometric series. So in a sense we get a closed-form formula. Perhaps that can be expressed as a linear combination of explicit whatever-nicci numbers. – André Nicolas Feb 21 '12 at 6:52
In fact, we can always express the sum as a linear combination of $n$ terms in the series and a constant. For the Fibonacci numbers, something nice happens and we only need one. – Yuval Filmus Feb 21 '12 at 7:05
Please do not post a complete solution to the problem here. Looks like the OP wants to solve: spoj.pl/problems/TETRASUM – user25383 Feb 21 '12 at 9:51
Upps, I hope there was nothing wrong with my answer... Why didn't the OP add a remark? (P.s. my firefox-browser does not "trust" that link. Is it ok to proceed to there? (added: I can open that site if I use "http" instead of "https")) – Gottfried Helms Feb 21 '12 at 9:57
I see no evidence that the OP got the problem from the SPOJ site; it’s a perfectly reasonable mathematical question independent of any programming aspects. – Brian M. Scott Feb 22 '12 at 6:45

3 Answers

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)\;.$$

-
if we take sum of first 9 terms of the series: then sum = 0+0+0+1+1+2+4+8+15=31 ; but by the formula it comes as : 221/3 – pranay Feb 21 '12 at 7:28
@pranay: The formula yields $\frac13(56+2\cdot 15+8-1)=\frac13(93)=31$. – Brian M. Scott Feb 21 '12 at 7:34
thanks a lot :) – pranay Feb 21 '12 at 8:56

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
-

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.

-