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.