Worst case running time in advance recurrence relation

Question

I am studying a graph algorithm research article where the worst case running time for a branching rule is expressed as, $$T\left(n\right)\:=\:T\left(n-2\right)\:+\:T\left(n-3\right)$$ $$=\:O\left(1.325^n\right)$$ How to calculate this type of recurrence relation?

Answer 1

Following the notation of this answer, $T(n)=x_n$ can be represented as

$$T(n) = \sum_{j=1}^3 \beta_j\lambda_j^{n-1}$$

where the $\beta_j$ depend on the initial values (which are unknown), and the $\lambda_j$ are solutions of the characteristic polynomial of the linear recurrence. Namely, in your case they satisfy:

$$\lambda^3 = 0\cdot\lambda^2+1\cdot\lambda^1+1\cdot\lambda^0 = \lambda+1\tag 1$$

This means the magnitude of $T(n)$ is dominated by (the absolute value of) the largest solution of (1), which is

$$\lambda_1\approx1.324717957244746$$

so that

$$T(n) \in {\cal O}(1.324718^n)$$

The other two solutions are complex with absolut value smaller than $\lambda_1$:

$$\lambda_{2,3}\approx-0.66236 \pm 0.56228 i,\qquad|\lambda_{2,3}|\approx 0.868838$$

So not only is $\lambda_1$ the dominating eigenvalue, it's also the case that the contributions of the other eigenvalues will be arbitrarily small as $n$ grows.