### Hd7's blog

By Hd7, history, 7 months ago, ,

I'm solving this Vietnamese problem which ask to calculate sum of first $n$ Tribonacci Number.
Tribonacci Number:

$\begin{cases}T_n = T_{n-1} + T_{n-2} + T_{n-3}& (n > 3)\\T_1 = 1, T_2 = 2, T_3 = 3\end{cases}$

Let $S_n$ is the sum of first $n$ Tribonacci.

$S_n = T_1 + T_2 + ... + T_n$

.
How to calculate $S_n$ with time complexity less than linear.
I have searched for it and found out we can use matrix multiplication to solve it with $O(log\ n)$. But with Fibonacci, we can based on relation between $F_n$ and $S_n$, $S_n = F_{n+2} - 1$. This article.
Could you help me figure out the relation between $T_n$ and $S_n$ in Tribonacci Number.

• +4

 » 7 months ago, # | ← Rev. 2 →   0 You can easily derive that $S_n = S_{n-1} + S_{n-2} + S_{n-3} + T_3 - T_1$or $(S_n+1) = (S_{n-1}+1) + (S_{n-2}+1) + (S_{n-3}+1)$And then use matrix expontiation with initial conditions $(S_1+1) = 2, (S_2+1) = 4, (S_3+1) = 7$Sorry, I can't find the simple relation between $S_n$ and $T_n$.UPD Seems the sequence ${S_n}+1$ is the same one as for the standartd Tribonacci numbers with some index offset.
•  » » 7 months ago, # ^ |   0 Thank you, I solved it using matrix exponentiation with using 4x4 matrix, $S_n = S_{n-1} + T_n = S_{n-1} + T_{n-1} + T_{n_2} + T_{n-3}$
 » 7 months ago, # |   +5 S(n)=(T(n+2)+T(n))/2 — 1
•  » » 7 months ago, # ^ |   0 Could you prove it?
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 Induction: $S_{n} = \frac{T_{n + 2} + T_{n}}{2} - 1$ $S_{n + 1} = S_{n} + T_{n + 1} = \frac{T_{n + 2} + T_{n}}{2} - 1 + T_{n + 1}$ $S_{n + 1} = \frac{2 T_{n + 1} + T_{n + 2} + T_{n}}{2} - 1$ $S_{n + 1} = \frac{(T_{n + 1} + T_{n + 2} + T_{n}) + (T_{n + 1})}{2} - 1$ $S_{n + 1} = \frac{T_{n + 3} + T_{n + 1}}{2} - 1$And it's easy to see that n = 1 works.
 » 7 months ago, # | ← Rev. 2 →   +8 It can be solved with matrix multiplication, just maintain $T_{n-3},T_{n-2}, T_{n-1}, S_{n-1}$ and multiply by matrix $M$ to go to $T_{n-2},T_{n-1}, T_{n}, S_{n}$. Try to find matrix $M$ by yourself)
•  » » 7 months ago, # ^ |   0 I did it! M is. $\begin{bmatrix}1 & 1 & 1 & 0 \\1 & 0 & 0 & 0 \\0 & 1& 0 &0 \\1 &1 &1 &1 \end{bmatrix}$