# Derivation of a formula for discrete time case

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!

-
The power of $A$ inside the summation should be $k-j$. It is a convolution. – copper.hat Nov 19 '12 at 0:35

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.
Write out a few terms of the solution and guess the pattern $x_1 Ax_0+B u_0$, $x_2 = Ax_1+B u_1 = A^2 x_0 + A B u_0 + Bu_1$, etc... Alternatively, you could use the $z$-transform, but guess & prove is fairly straightforward. – copper.hat Nov 19 '12 at 0:32