# Find the pattern in raising the matrix to a power

Given a matrix $A = \begin{pmatrix} 1 && 1 && 2 \\ 0 && 1 && 1 \\ 0 && 0 && 1 \end{pmatrix}$ determine the general formula for $A^k$ . I tried to solve it by induction and therefore computed the first steps up to $A^4$. The diagonal seems to stay constantly at 1, while $a_{12}$ and $a_{23}$ are equal to $k$. What I can't figure out is $a_{13}$. I've computed it for $A, A^2, A^3, A^4$ and the values are $2, 5, 9, 14, 20$.

How can I find the general pattern and prove it? Is there a general algorithm for finding $A^k$ where $A \in M_{i,j}(C)$ where M is the set of all matrixes that can be formed with elements from $C$.

-
Hint: $5-2=3$, $9-5=4$, $14-9=5$, $20-14=6$, $\ldots$ –  njguliyev Oct 21 '13 at 15:08

Note that your matrix $A$ has a special form, we have $A = \def\Id{\mathop{\rm Id}\nolimits}\Id{} + N$, where $N$ is a strictly upper triagonal matrix. Hence $N^3 = 0$, an therefore, by the binomial theorem (note $\Id$ and $N$ commute): $$A^k = (\Id + N)^k = \sum_{i=0}^k \binom ki N^i \Id^{k-i} = \Id + kN + \frac{k(k-1)}2 N^2$$ In general (look for Jordan normal form) you can write any matrix $A \in \mathbb C^{n\times n}$ as $A = S^{-1}(\Lambda + N)S$ where $S$ is invertible, $\Lambda$ diagonal, $N$ has only $1$ as entries and only on the first superdiagonal, and $\Lambda N = N \Lambda$.

-
Note that the space of upper triangular matrices is closed under multiplication, so we need only worry about $[A^{k}]_{ij}$ for $i\le j$. Then just work out the relevant difference equations.
We have $[A^{k}]_{ii} = 1$, $[A^{k+1}]_{12} = [A^{k}]_{12} + 1$, $[A^{k+1}]_{21} = [A^{k}]_{21} + 1$, $[A^{k+1}]_{13} = [A^{k}]_{13} + [A^{k}]_{12}+ 2$.
The second and third equations shows that $[A^{k}]_{12} = [A^{k}]_{21} = k$, so the fourth equation becomes $[A^{k+1}]_{13} = [A^{k}]_{13} + k+ 2$, from which we get $[A^{k}]_{13} = \frac{1}{2}k(3+k)$.