Is this true of all linear recurrences? Is it true that any linear recurrence $f_n$ can be written as:
$$f_n = \sum_{i=1}^{k} \alpha_i r_i^n$$
where $f_n$ is a linear recurrence of degree $k$ and $r_i$ represents a root of the characteristic polynomial, which can be uniquely described by the coefficients of the recurrence? (for example the recurrence $f_n = 10f_{n-1} - 3f_{n-2}$ has characteristic polynomial $1-10x+3x^2$).
The $\alpha$ terms would be solved through system of equations assuming you knew the first $k$ values of the recurrence.

First, I think you mean "linear homogeneous recurrence with constant coefficients". 
Second, the answer is no, but only just barely. Assuming the $r_i$ can be complex, the only problem arises when the $r_i$ are duplicated. In this case not all solutions to the recurrence are of this form. For example, $f_n - 2f_{n-1} + f_{n-2} = 0$ has one solution $f_n = f_0$. Yet there is clearly a solution to this recurrence with, say, $f_0=0,f_1=1$. It turns out that in these cases, the additional "missing" solutions to the recurrence are of the form $n r^n,n^2 r^n,\dots$; thus a root of multiplicity $k$ contributes $k$ linearly independent solutions to the recurrence.
