Powers of a companion matrix

First powers.
$$A^2 = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix},$$
$$A^3 = A^2 A = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 2 & 3 \end{pmatrix}.$$

Pattern. The entries are Fibonacci numbers $F_0=0, F_1=1, F_2=1, F_3=2, F_4=3, \ldots$:
$$A^k = \begin{pmatrix} F_{k-1} & F_k \\ F_k & F_{k+1} \end{pmatrix}.$$

Induction. Base case $k=1$: $A = \begin{pmatrix} F_0 & F_1 \\ F_1 & F_2 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$. Correct. Inductive step:
$$A^{k+1} = A^k A = \begin{pmatrix} F_{k-1} & F_k \\ F_k & F_{k+1} \end{pmatrix}\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} F_k & F_{k-1}+F_k \\ F_{k+1} & F_k+F_{k+1} \end{pmatrix}.$$
Using $F_{k-1}+F_k = F_{k+1}$ and $F_k+F_{k+1} = F_{k+2}$, we get
$$A^{k+1} = \begin{pmatrix} F_k & F_{k+1} \\ F_{k+1} & F_{k+2} \end{pmatrix}.$$

Conclusion. The formula holds for all $k \ge 1$.