Get the $n$th term of a sequence $1$, $2$, $4$, $7$, $13$, $24$, $\ldots$

Question

I have a sequence: $1$, $2$, $4$, $7$, $13$, $24$, $44$, $81$, and I think it's like a Fibonacci sequence, however you add three numbers together and not two ("Tribonacci"?). So: $$ v_n = v_{n-1} + v_{n-2} + v_{n-3}, $$ where $v_0=1$, $v_1=1$ and $v_2=2$.

I begin from the proof of the $n$th term of the Fibonacci sequence, and I find that: $$ \begin{bmatrix}1 & 1 & 1\\1 & 0 & 0\\0 & 1 & 0 \end{bmatrix}^n \begin{bmatrix}2 \\1\\ 1\end{bmatrix} = \begin{bmatrix}v_{n+2} \\v_{n+1}\\ v_n\end{bmatrix} = \mathbf{A}^n\mathbf{x} $$

$$ \mathbf{A}^n = \mathbf{PD}^n\mathbf{P}^{-1}$$ and $$ \mathbf{D}^n = \begin{bmatrix}\lambda_0^n &0&0\\0&\lambda_1^n&0\\0&0&\lambda_2^n\end{bmatrix}. $$

From $\det(\lambda I-A)=0$, I got that $\lambda_0=0$, $\lambda_1=1$ and $\mathbf{x}=0$

I got stuck here. Can anybody help me where I make a mistake?

Answer 1

I would honestly just solve the recurrence rather than dealing with matrices. The characteristic polynomial is: $\lambda^{3} - \lambda^{2} - \lambda - 1 = 0$.

This gives us eigenvalues $\lambda = 1.8393, -0.41964 \pm .60629i$.

This gives us a general form solution $v_{n} = A(1.8393)^{n} - B(0.41964)^{n}cos(0.60629n) - C(0.41964)^{n}sin(0.60629n)$.

Now plug in your initial values and solve for $A, B, C$:

$v_{0} = 1 = A - B$
$v_{1} = 1 = 1.8393A - 0.41964B * cos(0.60629) - 0.41964C * sin(0.60629)$
$v_{2} = (1.8939)^{2} * A - (0.41964)^{2} * (Bcos(0.60629 * 2) + Csin(0.60629 * 2))$

Answer 2

Use generating functions (what else? ;-). Write the recurrence as $t_{n + 3} = t_{n + 2} + t_{n + 1} + t_n$ with $t_0 = 0$, $t_1 = 1$, $t_2 = 2$; define $T(z) = \sum_{n \ge 0} t_n z^n$. Multiply the recurrence by $z^n$, sum over $n \ge 0$, and recognize the resulting sums: $$ \frac{T(z) - t_0 - t_1 z - t_2 z^2}{z^3} = \frac{T(z) - t_0 - t_1 z}{z^2} + \frac{T(z) - t_0}{z} + T(z) $$ Solving for $T(z)$: $$ T(z) = \frac{z + z^2}{1 - z - z^2 - z^3} $$ Descartes' rule of signs tells us there is at most one positive root and at most two negative ones. It turns out there is a real root and two complex ones. The expressions given by Cardan's formula are ghastly... numerically the real root is $0.5436890126920764$ (thus $t_n \sim c \cdot 1.839286755214161^n$, from $t_6 = 24$ you get $c \approx 0.62$).

maxima did most of the (heavy and otherwise) lifting.