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.

You can easily derive that

or

And then use matrix expontiation with initial conditions

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.

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}$$$

S(n)=(T(n+2)+T(n))/2 — 1

Could you prove it?

Induction:

And it's easy to see that n = 1 works.

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)

I did it! M is.