Generalization for Fibonacci-like sequences's explicit formula. Contex:
I saw the procedure of finding an explicit formula for the n'th Fibonacci number, something like:
assume $ a_n = \alpha^n$ which provides $\alpha^2 - \alpha - 1=0 \rightarrow \alpha_{1,2} = \frac{1\pm\sqrt5}{2}$
and then given $a_0 = 0, a_1 = 1$ you solve a 2D linear system of equations:
$$
\left\{\begin{matrix} & A*(\alpha_1)^0 + B*(\alpha_2)^0 = 0& \\ & A*(\alpha_1)^1 + B*(\alpha_2)^1 = 1& \end{matrix}\right.
$$ Yielding $ A = \frac{1}{\sqrt 5}, B = -\frac{1}{\sqrt5}$
And thus$ a_n = (\frac{1}{\sqrt 5})*(\frac{1+\sqrt5}{2})^n + (-\frac{1}{\sqrt5})*(\frac{1-\sqrt5}{2})^n $
So I did the similar process with a siries $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ and found an explicit formula for $a_n$ (given $a_0, a_1, a_2$).
Actual question:
So I was trying to find a general formula for $a_n$ if
$a_n = \sum_{i=1}^{k} (a_{n-i}) $ and given $a_1 = x_1, a_2 = x_2, ... a_k = x_k$.
So I started as before: $ a_n = \alpha^n$ yielding:
$ \alpha^n = \sum_{i=1}^{k} (\alpha^{n-i}) $ and dividing by $\alpha^{n-k}$ gives: $ \alpha^k = \sum_{i=1}^{k} (\alpha^{k-i}) = \sum_{i=0}^{k-1} (\alpha^{i}) = \frac{\alpha^k-1}{\alpha -1} \rightarrow\\ \alpha^k*(\alpha-1) = \alpha^k - 1 \rightarrow\\ \alpha^{k+1} - 2\alpha^k+1=0\\$
And this is where I'm stuck. If I could solve here for $\alpha$ as a function of k then I could solve the following set of linear equations(by inverting the matrix) :
$$
\begin{bmatrix}
 \alpha_1&\alpha_2  & ... &\alpha_k \\ 
 (\alpha_1)^2&(\alpha_2)^2  & ... & (\alpha_k)^2\\ 
 ...& ... & ... &... \\ 
 (\alpha_1)^k& (\alpha_2)^k &...  &(\alpha_k)^k 
\end{bmatrix} *
\begin{bmatrix}
P_1\\ 
P_2\\ 
...\\ 
P_k
\end{bmatrix} = 
\begin{bmatrix}
x_1\\ 
x_2\\ 
...\\ 
x_k
\end{bmatrix}
$$
And thus find an explicit formula for $a_n$ (namely $a_n = \sum_{i=1}^k (P_i * (\alpha_i)^n)$)
So I would love help solving for $\alpha$ or any information regarding this idea. Thank you!
 A: I would like to challenge you about whether you really need some expression in terms of radicals for the roots of $$x^k - x^{k-1} - x^{k-2} - \ldots - x - 1 = 0$$
We know this equation has $k$ roots. By comparing it with its derivative, we can determine if it has any multiple roots. (If so, then some adjustment to the scheme is necessary, as you must have $k$ distinct roots to match all possible initial conditions by a linear combination of powers of those roots).
Methods exist for estimating those roots to any desired accuracy. So we can calculate what we need. And in fact expression by radicals is no better for this. $\sqrt 5$ is just a notation that means "the positive root of the equation $x^2 - 5 = 0$." If we want to calculate with it, then we have to estimate it as well.
From a mathematical standpoint, "$\alpha_i$ is the $i$-th root of the polynomial $P(x)$ when ordered first by magnitude and second by argument in $[0,2\pi)$" is just as valid a definition for $\alpha_i$ as "the positive root of $x^2 - 5$" is for $\sqrt 5$.
If you want to calculate the sequence elements $a_n$ for some choice of the initial $k$ values, using the recursion formula to do it will be faster and easier for values $< 2^{64}$ than attempting the same level of accuracy from a Binet-style formula of powers of the roots.
For values beyond that, you really just need to know the root or roots with highest magnitude. For large $n$, they will dominate the Binet-style formula, with all the other terms making miniscule corrections. None of this will be made any easier by having an expression by radicals (or some other expression in terms of esoteric functions) for the roots.
"closed-form" expressions are something of a chimera in mathematics. They are nice when we have them, but beyond the basics, they are seldom of much use in understanding a subject.

Edit: Look at the case for $k=3$ as an example. The equation is
$$p(x) = x^3 - x^2 -x -1 = 0$$
This has derivative $$p'(x) = 3x^2 - 2x - 1$$ and we can use the Euclidean algorithm to find the gcd of $p(x)$ and $p'(x)$, which is $1$, showing that $p(x)$ and $p'(x)$ have no common root. So $p(x)$ has three distinct roots $\alpha$, for each of which $a_n = \alpha^n$ is an independent solution of the recursion formula $a_n = a_{n-1} + a_{n-2} + a_{n-3}$, and so every solution must be a linear combination of them. (If $p(x)$ had a repeated root, we would not have three independent solutions and would need to be a bit more sophisticated.)
Starting at $x = 2$, it takes only four iterations of Newton's method to arrive at $$\alpha \approx 1.83928675521416$$
Dividing out $x - \alpha$ from $p(x) = 0$ gives a quadratic which can be solved to find the other two roots $$\beta \approx -0.41964337760708 + i0.606290729207197$$
and its conjugate. Now $|\beta| \approx 0.737352705760326$
Thus any real sequence $a_n$ satisfying the recursion can be expressible as
$$a_n = A\,\alpha^n + B\,\beta^n + \overline B\,\overline\beta^n$$
for some real $A$, complex $B$. If $a_n$ is not always real, then $A$ need not be real, and $\overline B$ can be an arbitrary complex number unrelated to $B$.
Because $\alpha > 1 > |\beta|$, the contributions of the first term grows as $n$ increases, while the contributions of the other two terms decrease. So for high $n, a_n \approx A\alpha^n$.
The information above gives you a pretty good description of how $a_n$ behaves. Actually knowing that
$$\alpha = \frac{1 + \sqrt[3]{2} + 2\sqrt[3]4}3\\
\beta = \frac{1 + \omega\sqrt[3]{2} + 2\omega^2\sqrt[3]4}3$$
where $\omega = \frac{-1 - i\sqrt 3}2$ doesn't offer much in the way of additional clarity.
