Блог пользователя Hd7

Автор Hd7, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Could you prove it?

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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