2
$\begingroup$

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.

  • 0
    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.2012-02-21
  • 0
    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.2012-02-21
  • 0
    OP is SPOJ user http://www.spoj.pl/users/streetfi8er/. He asked his question only 1 or 2 days after the problem has been published and if you look at the quality and quantity of the questions he asked about other SPOJ problems in the SPOJ forum, it is more than obvious.2012-02-22
  • 0
    Please do not post a complete solution to the problem here. Looks like the OP wants to solve: https://www.spoj.pl/problems/TETRASUM/2012-02-21
  • 0
    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"))2012-02-21
  • 2
    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.2012-02-22

3 Answers 3

5

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

  • 0
    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/32012-02-21
  • 0
    @pranay: The formula yields $\frac13(56+2\cdot 15+8-1)=\frac13(93)=31$.2012-02-21
3

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
1

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.