Given is the following discrete system
$$\begin{align*} &x(k + 1) = Ax(k) + Bu(k)\\ &x(0) = x_0\;. \end{align*}$$
How do we prove that the explicit solution formula for $x(k)$ (analogously to the variation of constants formula in the continuous time case) is
$$A^kx_0+\sum_{j=1}^kA^{j-k}Bu(j-1)\;?$$
Thanks a lot!
Your formula is incorrect. The correct formula is $\phi_k = A^kx_0+\sum_{j=0}^{k-1} A^{k-j-1}Bu_{j}$, where the summation is taken to be $0$ when $k=0$.
With this convention, you have $\phi_0 = x_0$, and the induction step gives \begin{eqnarray} \phi_{k+1} & = & A^{k+1} x_0+\sum_{j=0}^{k} A^{k-j}Bu_{j}\\ &=& A(A^k x_0+\sum_{j=0}^{k-1} A^{k-j-1}Bu_{j}) + Bu_k\\ & = & A \phi_k+B u_k \end{eqnarray} Hence $\phi$ satisfies the same difference equation as $x$ with the same initial condition, hence $\phi_k = x(k)$ for all $k \geq 0$, that is $\phi$ is the solution.