Let $A=(a_{i}^{j})\in M_{n \times n}(\mathbb{R})$, with $a_{i}^{j} = 1$ if $i -j = 1$, and $0$ otherwise. I'm asked to derive the formula/general term of the matrix power and prove it by induction. I've conjectured that if $A^{k} = (b_{i}^{j}) \in M_{n \times n}(\mathbb{R})$, then $b_{i}^{j} = 1$ if $i -j = k$, and $0$ otherwise.
I'm able to prove the initial case, however, I don't know how to write $A^{k-1}$ in matrix form in order to prove the induction step. How does one represent the $n \times n$ matrix?
We can use your conjecture (for a matrix $(b_i^j) = A^k$ we have $b_i^j = 1$ if $i-j=k$ and $0$ elsewhere), as the induction hypothesis, which means you can use it on the "smaller problem" $A^{k-1}$ to show it is also true for a "slightly larger problem" $A^k$. I will show where I use it in the proof below.
The following proof uses induction and direct calculation, and assumes the element $a_i^j$ is in the $i$th row and the $j$th column of matrix $(a_i^j)$.
Let $(c_i^j)=A^{k-1}$, and suppose that $c_i^j = 1$ if $i-j=k-1$, and $0$ otherwise (i.e. we assume that your conjecture is true for some "smaller problem", this is the induction hypothesis). Then we prove that $(b_i^j) = A^k$ (a "slightly larger problem") satisfies the property $b_i^j = 1$ if $i-j=k$, and $0$ otherwise.
Using $A^k = A^{k-1}A$, we see that $$b_i^j = \sum_{m=1}^n c_i^ma_m^j.$$ We know that every row or column in the matrices $A$ and $A^{k-1}$ has at most one $1$, and zeros elsewhere ($*$). The sum can therefore only equal 1 or 0.
Choose $i$ and $j$, and suppose that the sum evaluates to $1$. Property ($*$) then tells us that one of the terms must equal one, i.e. there exists an $l$ such that $c_i^la_l^j = 1$. Then both factors must equal $1$, which means $i-l=k-1$ (we use the induction hypothesis here) and $l-j=1$. Adding these last two requirements yields $i-j=k$.
Choose now $i$ and $j$ such that $i-j=k$, and choose $m = i-k+1$ (1). Adding these equalities yields $m-j = 1$ (2). From (1) we also get $i-m=k-1$, which means $c_i^m=1$ (induction hypothesis). We know that (2) means that $a_m^j = 1$. We thus get $c_i^ma_m^j = 1$. Using ($*$), we know that the other terms in the sum must be zero, which means $b_i^j=1$.
We have now proven that $b_i^j$ can only be zero or one, and that it is one if and only if $i-j=k$. Hence, when $i-j\neq k$, it must be zero. This concludes the proof.