Hd7's blog

Sum of first n Tribonacci Number?
By Hd7, history, 5 years ago, In English

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.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can easily derive that

$$$ S_n = S_{n-1} + S_{n-2} + S_{n-3} + T_3 - T_1 $$$

or

$$$ (S_n+1) = (S_{n-1}+1) + (S_{n-2}+1) + (S_{n-3}+1) $$$

And then use matrix expontiation with initial conditions

$$$ (S_1+1) = 2, (S_2+1) = 4, (S_3+1) = 7 $$$

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you prove it?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Induction:

      $$$S_{n} = \frac{T_{n + 2} + T_{n}}{2} - 1$$$
      $$$S_{n + 1} = S_{n} + T_{n + 1} = \frac{T_{n + 2} + T_{n}}{2} - 1 + T_{n + 1}$$$
      $$$S_{n + 1} = \frac{2 T_{n + 1} + T_{n + 2} + T_{n}}{2} - 1$$$
      $$$S_{n + 1} = \frac{(T_{n + 1} + T_{n + 2} + T_{n}) + (T_{n + 1})}{2} - 1$$$
      $$$S_{n + 1} = \frac{T_{n + 3} + T_{n + 1}}{2} - 1$$$

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

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did it! M is.

    $$$\begin{bmatrix}1 & 1 & 1 & 0 \\1 & 0 & 0 & 0 \\0 & 1& 0 &0 \\1 &1 &1 &1 \end{bmatrix}$$$
    → Reply