Given a matrix $A$ . Calculate $A^{50}$ I have given matrix with me as follows . I need to calculate $A^{50}$ . Hint is to diagonaize it ,but since it has repeated eigen values so can't be diagonalized.Can any1 help me with this 
$$A=\left[\matrix{ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 }\right]$$
 A: Hint: Compute the first powers and guess
$$A^n=$$  \begin{pmatrix} 1 & n & \frac{n(n+1)}{2} \\ 0 & 1 & n \\ 0 & 0 & 1 \end{pmatrix}
Then prove this guess with induction.
A: Instead of diagonalization, one can compute $A^{50}$ using the fact $A$ is upper triangular and hence its off-diagonal part $B = A - I$ is nilpotent. i.e
$$B^3 = (A-I)^3 = 0$$
This implies
$$A^{50} = (I + B)^{50} = I + \binom{50}{1} B + \binom{50}{2} B^2 + 0 + \ldots\\
= \begin{bmatrix}1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix}
+ 50 \begin{bmatrix}0 & 1 & 1\\ 0 & 0 & 1 \\ 0 & 0 & 0\end{bmatrix}
+ 1225 \begin{bmatrix}0 & 0 & 1\\ 0 & 0 & 0 \\ 0 & 0 & 0\end{bmatrix}
= \begin{bmatrix}1 & 50 & 1275\\ 0 & 1 & 50 \\ 0 & 0 & 1\end{bmatrix}
$$
A: Since the matrix is not actually diagonalizable, I will show it in a different way.
Since $A$ is upper triangular, any power of $A$ is also upper triangular. Note that pre-multiplication by the matrix $A$ performs the following operations when another $3\times3$ matrix:
$$R_1\to R_1+R_2+R_3$$
$$R_2\to R_2+R_3$$
Based on this rule and the fact that it is upper triangular, it is clear that any powers of $A$ have a diagonal of $1$s. So far we have that
$$A^n=\pmatrix{1&a_{12}&a_{13}\\0&1&a_{23}\\0&0&1}$$
Now note that $a_{12}$ and $a_{23}$ just have $1$ added after every multiplication by $A$. If we do this $n$ times, we have
$$A^n=\pmatrix{1&n&a_{13}\\0&1&n\\0&0&1}$$
As for $a_{13}$, note that multiplying by $A$ adds $n$ to it. combined with the fact that we start with $a_{13}=1$, $a_{13}$ is actually the sum of the first $n$ numbers which is $\frac{n(n+1)}{2}$. Hence we have
$$A^n=\pmatrix{1&n&\frac{n(n+1)}{2}\\0&1&n\\0&0&1}$$
Remark:
This method has an elegant generalisation. Consider the upper triangular $n\times n$ matrix.
$$ U =
\begin{pmatrix}
1 & 1 & 1 & \ldots & 1  \\
        & 1 & 1 & \ldots & 1  \\
        &         & \ddots  & \ddots & \vdots   \\
        &         &         & \ddots & 1\\
        &         &         &        & 1
\end{pmatrix}$$
 Then if $P_0(k)=1$ and $P_n(k) = P_{n-1}(1)+P_{n-1}(2)+\cdots+P_{n-1}(k)$
, it can be shown that $P_n(k)={{n+k-1}\choose n}$. Then
$$A_n^k=
\begin{pmatrix}
P_0(k) & P_1(k) & P_2(k) & \ldots & P_{n-1}(k)  \\
        & P_0(k) & P_1(k) & \ldots & P_{n-2}(k)  \\
        &         & \ddots  & \ddots & \vdots   \\
        &         &         & \ddots & P_1(k)\\
        &         &         &        & P_0(k)
\end{pmatrix}=
\begin{pmatrix}
1 & {{k}\choose 1} & {{k+1}\choose 2} & \ldots & {{n+k-1}\choose n}  \\
        & 1 & {{k}\choose 1} & \ldots & {{n+k-2}\choose n}  \\
        &         & \ddots  & \ddots & \vdots   \\
        &         &         & \ddots & {{k}\choose 1}\\
        &         &         &        & 1
\end{pmatrix}
$$
