Does a fundamental solution set exist for homogeneous first-order difference equations? 
When $A$ is diagonalisable, $\vec{x}_{k+1}=A\vec{x}_k$ implies that
  $\vec{x}_k = c_1\lambda_1^k\vec{v}_1 +...+c_n\lambda_n^k\vec{v}_n$
  because an eigenbasis exists and any $\vec{x}$ can be decomposed into
  a linear combination of $A$'s eigenvectors.

But when $A$ is not diagonalisable, is there a related general formula for (or a general technique to find) $\vec{x}_k$ in terms of $A$'s eigenvalues and eigenvectors?
I ask this because I have just learnt that for the differential system $\dot{\vec{x}}=A\vec{x}$, a fundamental solution set always exists so that even when $A$ is defective, $\vec{x}$ can still be expressed in terms of $A$'s eigenvectors and eigenvalues.

It works pretty much the same way as for differential equations. Let $P^{-1}AP=J$ where $J$ is in Jordan form. Then $$x_k=A^kx_0=PJ^kP^{-1}x_0$$ and you just need to understand powers of a matrix in Jordan form, and the relation of $P$ to the eigenvectors and generalized eigenvectors. 
EDIT: Here's the simplest example. Say $$A=\pmatrix{\lambda&1\cr0&\lambda\cr}$$ Then $$A^n=\pmatrix{\lambda^n&n\lambda^{n-1}\cr0&\lambda^n\cr}$$ Let $v_1$ be the eigenvector $(1,0)$, let $v_2$ be the generalized eigenvector $(0,1)$. Then $$A^nv_1=\lambda^nv_1\quad A^nv_2=n\lambda^{n-1}v_1+\lambda^nv_2$$ so 
$$A^n(c_1v_1+c_2v_2)=(c_1\lambda^n+c_2n\lambda^{n-1})v_1+c_2\lambda^nv_2$$
But do check my arithmetic.
MORE EDIT: We can rewrite that last expression as $$x_n=c_1\lambda^nv_1+c_2\lambda^n((n/\lambda)v_1+v_2)$$ which looks a little more like the form you've given for the analogous difference equation.   
