Finding the general form of matrix ($A^n$) So i had to solve a problem for which i had to find $A^n$
Where A= $$
\begin{bmatrix}
1 & 0 & 0 \\
2 & 1 & 0 \\
4 & 2 & 1 \\
\end{bmatrix}
$$

So what i did was find $A^2$=
$$
\begin{bmatrix}
1 & 0 & 0 \\
4 & 0 & 0 \\
12 & 4 & 1 \\
\end{bmatrix}
$$

Then $A^3$=
$$
\begin{bmatrix}
1 & 0 & 0 \\
6 & 1 & 0 \\
24 & 6 & 1 \\
\end{bmatrix}
$$

so then i noticed the pattern and proved it by induction.
$A^n$= 
$$
\begin{bmatrix}
1 & 0 & 0 \\
2n & 1 & 0 \\
2n(n+1) & 2n & 1 \\
\end{bmatrix}
$$

Now this is a really troublesome method to solve these kind of questions. First of all it's not easy to notice the pattern . Then you could have to always guessed wrong ,so you have also verify with induction.
So i want to know is there a better to solve this question.  Does that method work here only or is it possible to find $A^n$ for any A(a method which always work).I would be happy to know what you keep in mind or tricks you use while solving these kind of problems. Links are also welcomed.
And again thankyou all for your help.
 A: Let $J=\pmatrix{0&0&0\\ 2&0&0\\ 0&2&0}$. Then $J^3=0$ and
$$
A=I+J+J^2=1+J+J^2+J^3+\cdots=(I-J)^{-1}.
$$
Thus
\begin{aligned}
A^n&=(I-J)^{-n}=\left[(I-J)^n\right]^{-1}\\
&=\left(I-nJ+\binom{n}{2}J^2+\binom{n}{3}J^3+\cdots\right)^{-1}\\
&=\left(I-nJ+\binom{n}{2}J^2\right)^{-1}\\
&=I+nJ+\left(n^2-\binom{n}{2}\right)J^2\\
&=\pmatrix{1&0&0\\ 2n&1&0\\ 2n(n+1)&2n&1}.
\end{aligned}
A: By the Cayley-Hamilton theorem, any $n \times n$ matrix $A$ satisfies its characteristic polynomial $P(x) = \det(x I - A)$.  Let $P(x) = x^n + \sum_{j=0}^{n-1} c_j x^j$.  Then we have the linear recurrence
$$A^k = - \sum_{j=0}^{n-1} c_j A^{k-n+j}$$
The solutions to this recurrence will be of the form
$$ A^k = \sum_i \lambda_i^k Q_i(k)$$
where $\lambda_i$ are the eigenvalues of $A$ and $Q_i$ is a matrix whose entries are polynomials of degree at most one less than the multiplicity of $\lambda_i$ as a root of $P$.  Thus in your case 
the only eigenvalue is $1$, with multiplicity $3$, so the entries are polynomials of degree $\le 2$.
