# Difficulty Finding $A^k$

Let $$A= \begin{bmatrix} 1& -1 & 1\\ 0 & 1 & 1 \\ 0 & 0 & 1\\ \end{bmatrix}$$. Compute $$A^k$$.

# My attempt

I'm trying to compute $$A^k$$ using this approach as follows: $$A=I+N= \begin{bmatrix} 1& 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}+ \begin{bmatrix} 0& -1 & 1\\ 0 & 0 & 1 \\ 0 & 0 & 0\\ \end{bmatrix}$$ with $$N^2= \begin{bmatrix} 0& 0 & -1\\ 0 & 0 & 0 \\ 0 & 0 & 0\\ \end{bmatrix}, \, \text{and} \, \, N^3= \begin{bmatrix} 0& 0 & 0\\ 0 & 0 & 0 \\ 0 & 0 & 0\\ \end{bmatrix}$$

Then, $$A^2=(I+N)^2=I+2N+N^2, \\ A^3=(I+N)^3=I+3N+3N^2, \\ A^4=(I+N)^4=I+4N+6N^2, \\ A^5=(I+N)^5=I+5N+10N^2, \\ A^6=(I+N)^5=I+6N+15N^2,$$

By induction, we can see $$A^k=(I+N)^k=I+kN+f[k]N^2$$. But, I couldn't figure out what $$f[k]$$ is. Any help?

• binomial coefficient $k$ choose $2,$ which become $k(k-1)/2$ – Will Jagy Sep 24 '18 at 0:30
• @WillJagy Exactly! It worked. Thank you. – Lod Sep 24 '18 at 0:46

How about this. Take the exponential function $$e^{tA}$$, where $$t$$ is some parameter $$e^{tA}=\sum_{k=0}^\infty\frac{t^kA^k}{k!}=e^{t(I+N)}= e^{tI}e^{tN}=e^t\left[I+tN+\frac{(tN)^2}{2}\right]$$ where we used the matrix identity $$e^{A+B}=e^Ae^B$$ that is valid when matrices $$A$$ and $$B$$ commute. Since the functions $$t^k$$ are linearly independent, we obtain $$A^k=I+kN+\frac{k(k-1)}{2}N^2$$
• That's even a better compact approach. However, I did not get how $t^2$ became $k(k-1)$. What is it that you mean with "the functions $t^k$ are linearly independent"? – Lod Sep 24 '18 at 1:26
• @Lod, you have to expand the exponential on the right side, the coefficients of $t^k$ on both sides of the equation have to be equal. The linear independence you can see from this: If you assume $\sum_{k=0}^\infty a_kt^k=0$ is valid for all $t$, this implies all $a_k=0$. To see this just take the $k$-th order derivative and then replace $t=0$. – minmax Sep 24 '18 at 1:37
You have written $$A=I+N$$, and you know that $$N^3$$ (and hence all higher powers) are zero. If $$X$$ and $$Y$$ are two matrices that commute with each other, then you can still use the bionomial theorem: $$(X+Y)^n=\sum_{i+j=n}\binom{n}{i} X^i Y^j$$
Because $$I$$ commutes with $$N$$, and because all the higher powers of $$N$$ vanish, we can apply the formula to get
$$(I+N)^n=\sum_{i+j=n}\binom{n}{j} N^j=I+nN+\binom{n}{2}N^2$$