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.