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

Tribonacci Number:

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

.

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.

Thanks for your reading.