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.
Thanks for your reading.

Tags #math, #tribonacci


  Rev. Lang. By When Δ Comment
en1 English Hd7 2019-10-29 14:27:24 821 Initial revision (published)