There's a more fundamental way to derive the exponential form: linear difference equations are analogous to linear differential equations, so we should look at them in terms of actions on some vector space of functions. Similarly, we should also look at eigenfunctions, which end up being of the form a_i*C_i^n for some constants C_i, a_i and, where i=0..{dimension of the nullspace of the overall difference operator}. You can then substitute that form into the equation to find out the C_i and a_i using the initial conditions.
It's exactly like solving a differential equation.
Another path is to look at formal power series, and a good book is Generatingfunctionology.
Knuth Oren and Patashnik's Concrete Mathematics covers the basics very well and goes into much more detail on finite difference calculus.
I'd wager to say there's nothing more fundamental about it. You are still finding eigenvalues and eigenvectors of a linear operator. The matrix is exactly the same.
It's more fundamental since you're working with the underlying vector space and linear operator vs representing it as a matrix over R^n, running a decomposition, then converting back. No need to change domains, but yes they are isomorphic (which is the point).
It's exactly like solving a differential equation.
Another path is to look at formal power series, and a good book is Generatingfunctionology.
Knuth Oren and Patashnik's Concrete Mathematics covers the basics very well and goes into much more detail on finite difference calculus.