Closed form for recurrence relation

Question

Is there a closed-form solution to the following recurrence:

$$T(n) = T(n-1) + T(n-3)$$

If yes, what is it and how can it be proven/derived?

If not, then why because a somewhat similar recurrence like fibonacci has closed-form solution.

Answer 1

The explicit formula looks like this: $$T(n) = a_1 x_1^n+a_2 x_2^n+a_3x_3^n,$$ where $x_{1,2,3}$ are the three roots of $x^3-x-1=0$ and $a_{1,2,3}$ are determined by the initial conditions.

But through my magic crystal ball I see that you do not really want an explicit formula, rather you need a method to calculte $T(n)$ in short time for inputs up to $n\approx 2^{64}$. The following method takes only $O(\ln n)$ time: The map $(T(n), T(n+1), T(n+2))^t\mapsto (T(n+1), T(n+2), T(n+3))^t$ is linear, i.e. given by some $3\times 3$ matrix $A$. Then we have $$(T(n), T(n+1), T(n+2))^t = A^n\cdot(T(0), T(1), T(2))^t$$ and we can find $A^n$ by repeated squaring in $O(\ln n)$ operations.

Answer 2

The characteristic equation $z^3=z^2+1$ has a real root, let $t$, and a pair of complex conjugate roots $p\pm iq$, or $re^{\pm i\theta}$ in polar form.

The general solution is $$T_n=At^n+B(re^{i\theta})^n+C(re^{-i\theta})^n.$$ Assuming that the initial values are real, so is the general solution, and by conjugation $$At^n+B(re^{i\theta})^n+C(re^{-i\theta})^n=A^*t^n+B^*(re^{-i\theta})^n+C^*(re^{i\theta})^n.$$ This shows that $A$ is real, and $B, C$ are complex conjugates. The general solution can be rewritten as $$T_n=at^n+(b-ic)(re^{i\theta})^n+(b+ic)(re^{-i\theta})^n=at^n+2r^n(b\cos(n\theta)+c\sin(n\theta)).$$ It has a pure exponential term and an oscillating exponential term.