I'm learning an algorithm, the algorithm takes as input a graph of n vertices, and recurse on some subgraphs.
the complexity analysis done by the author is based on using recurrent formula.
the equation $T(n) = T(n - 3) + 2T(n - 4) + 4T(n - 6)$ was produced by reviewing the possible recursive calls.
the author says that by solving this recurrence, the unique real positive root of the polynomial $x^6=x^3+2x^2+4$ is approximately $1.51433$.
So the complexity of the algorithm is $O(1.51433^n)$.
My question is how we can produce the equation from the recurrence formula.
Assume I would like to look for the solutions to the recurrence $T_n$ of the form $T_n = x^n$ for some $x \ne 0$. Plugging that into the recurrence, you get $$ x^n = x^{n-3} + 2x^{n-4} + 4x^{n-6} $$ and now cancel $x^{n-6}$ from both sides, yielding your polynomial.
Indeed, the resulting polynomial $x^6-x^3-2x^2-4$ has one positive root $r \approx 1.51432$ (as you can see on the Wolfram Alpha plot, so more accurately one would say that $$ T(n) = \Theta(r^n). $$