Sum of first n Tribonacci Number?

Revision en1, by Hd7, 2019-10-29 14:27:24

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.