There is a theorem on calculating the number of walks of length $k$ from one vertex $v_i$ to another $v_j$, which says that
Let $G=(V,E)$ be a graph with $V=\{v_1,\dots,v_n\}$ and adjacency matrix $A_G=(a_{ij})$. Let $k\in \mathbb{N}$ and let $1\le i,j\le n$. The number of walks of length $k$ from $v_i$ to $v_j$ is equal to the $(i,j)^{th}$ entry of the matrix $A_G^k$.
My first question is that what is $A_G^k$. I don't know what the superscript $k$ means. Other questions are related to the proof of this theorem.
The proof of the theorem is given below:
Prove by induction on $k$. When $k=1$, the result holds obviously. Assume that the result holds for $k$. Let $B=(b_{ij})=A_G^k$. Therefore, $A_G^{k+1}=BA=(c_{ij})$ and the $(i,j)^{th}$ entry of $A_G^{k+1}$ is $$c_{ij}=\sum_{l=1}^nb_{il}a_{lj}.$$ By the induction hypothesis, for all $1\le l\le n$, $b_{il}$ is the number of walks of length $k$ between $v_i$ and $v_l$. This value is added to $c_{ij}$ if and only if $\{v_l,v_j\}\in E$. Therefore, $c_{ij}$ counts the number of walks of length $k+1$ between $v_i$ and $v_j$.
Here comes my next question:
Why $A_G^{k+1}=BA$?
Any help is appreciated!