The problem is
Let $A$ be the $n \times n$ adjacency matrix of a graph $G=(V,E)$ on $n$ vertices, i.e. $A=(a_{ij})$ and $$a_{ij}=\begin{cases} 1 & ij\in E \\ 0 & ij\notin E \end{cases}$$ Show that the $i,j$ entry of $A^k$ is the number of $i-j$ walks in $G$ that use exactly $k$ edges.
I'm almost done but I don't quite believe my solution. Here's what I have.
Let $w_k(i,j)$ be the number of $i-j$ walks of length $k$. Clearly, $$w_{1}(i,j)=\begin{cases} 1 & ij\in E \\ 0 & ij\notin E \end{cases}$$ The number of $i-j$ walks of length $k$ equal to the number of walks of length $k-1$ from $i$ to a vertex in $N(j)$ where $N(j)$ is the set of vertices adjacent to $j$, so we have $$w_k(i,j)=\sum_{x \in N(j)}w_{k-1}(i,x)$$ Now,, $[A^k]_{ij}=[A^{k-1}A]_{ij}=[A^{k-1}]_i^T [A]_j$, where the subscripts denote columns of the matrix in brackets (since $A$ is symmetric and hence powers thereof are also symmetric). We can write this as $$[A^k]_{ij}=\sum_{l=1}^n[A^{k-1}]_{il}[A]_{lj}$$
And by the definition of $A$, this is equivalent to $$[A^k]_{ij}=\sum_{x\in N(j)}[A^{k-1}]_{ix}$$
Obviously these recursive definitions look very similar and I can't decide if I am done or not. How can I show that these are in fact are the exact same function?
You have the right idea, but you’ve not really made it clear. What you want to do is show by inductionn on $k$ that $w_k(i,j)=[A^k]_{ij}$ for all $i,j\in\{1,\ldots,n\}$. This is clearly the case for $k=1$. If $k>1$, and if it holds for $k-1$, then
$$\begin{align*} w_k(i,j)&=\sum_{\ell\in N(j)}w_{k-1}(i,\ell)\\ &=\sum_{\ell\in N(j)}[A^{k-1}]_{i\ell}&\text{induction hypothesis}\\ &=\sum_{\ell=1}^n[A^{k-1}]_{i\ell}[A]_{\ell j}&\text{since }[A]_{\ell j}=\begin{cases}1,&\ell\in N(j)\\0,&\ell\notin N(j)\end{cases}\\ &=[A^k]_{ij}\;, \end{align*}$$
and we’re home free.