Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
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. –  Brian M. Scott Feb 22 '12 at 6:45

3 Answers 3

up vote 5 down vote accepted

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

share|improve this answer
    
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
share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.