Hints for my try on an induction proof that a matrix $A$ to the power of $k$ equals to... So given is the following matrix $A$:
$$A=(a_{i,j})_{i,j=1,\cdots,n},a_{i,j}=
\begin{cases}
1,   & i=j=1\vee(i\ge2\wedge j=i+1)\\
\mu, & i=j\ge2\\
0,   & \text{else}\\
\end{cases}$$
Now prove by induction:
$$A^k=(a_{i,j}^{(k)})_{i,j=1,\ldots,n},a_{i,j}^k =
\begin{cases}
1,   & i=j=1\\
{k \choose j-i}\mu^{k-(j-i)}, & j\ge i\ge2 \wedge k+i>j\\
0,   & \text{else}\\
\end{cases}$$
Hints: $A^k=A\cdots A$ ($k$-times) and note that ${n\choose k}+{n \choose k-1} = {n+1 \choose k}$

My try:
Base case: $k=1:$ $A^1=A=a_{i,j}$, so we need to show equality of $a_{i,j}=a_{i,j}^{(1)}$:


*

*$i=j=1:$ $$a_{i,j}^{(1)}=1=a_{i,j}$$

*$i\ge2\wedge j=i+1$: $$a_{i,j}^{1}={{1}\choose{j-i}}\mu^{1-(j-i)}={{1}\choose{(i+1)-i}}\mu^{1-((i+1)-i)}=1\mu^{0}=1=a_{i,j}$$

*$i=j\ge2:$ $$a_{i,j}^{(1)}={{1}\choose{j-i}}\mu^{1-(j-i)}={{1}\choose{i-i}}\mu^{1-(i-i)}=\mu=a_{i,j}$$


** induction step from $k+1\to k$ **
$$A^{k+1}=A\cdot A^{k}=^{\text{Induction}}A\cdot(a_{i,j}^{(k)})_{i,j=1,\cdots,n}=\left(\sum^n_{p=1}{a_{t,p}\cdot a_{p,s}^{(k)}}\right)_{t,s=1,\cdots,n}=???$$
Now what? How can I proceed? Another case analysis like in the base case? But what cases? (please don't post full answers, but hints)
 A: Wow, this is a nasty problem. A lot of brute force work to be done. My best general advice is to write everything out explicitly, clearly, and accurately; constantly differentiate between terms belonging to different matrices and how they are distinctly defined; and consider the cases. Your approach is spot on. There's not much more conceptually to realize; you just need to spot the trick for reducing the sums associated with each entry $a_{i,j}^{(k+1)}$. 
Now, if you want some more specific tips, let's go back to the sum which you've correctly associated to $a_{i,j}^{(k+1)}$. I'm not sure why you used $s,t$ instead of $i,j$ in the sum, but it'll be very important to clearly visualize the connection between $a_{i,j}^{(k+1)}$ and its corresponding sum. Writing out the sum in terms of $i,j$ gives
$$a_{i,j}^{(k+1)} = \sum_{p=1}^{n}a_{i,p}\cdot a_{p,j}^{(k)}.$$
So, where to go from here? As you've guessed in the details, you'll need to consider the $(i,j)$ corresponding to each case in the theorem you're trying to prove. In order to establish the relationship for each case, I strongly urge you to fix $(i,j)$ to certain specific values when able to, or to simply fool around with patterns. 
Let's start with the simplest case: $(i,j) = (1,1)$. In light of the previous advice, write out $a_{1,1}^{k+1}$ explicitly as
$$a_{1,1}^{(k+1)} = \sum_{p=1}^{n}a_{1,p}\cdot a_{p,1}^{(k)}.$$
Thankfully, we can dissect this intimidating expression by paying attention to the definition of terms in $A$. For starters, we immediately have that $a_{1,1} = 1$. But more importantly, we can also note that the index $i$ is fixed at $i=1$ for all terms $a_{1,p}$ belonging to $A$ in the above sum. This is useful information because it indicates that $i < 2$ for all terms belonging to $A$, from which it follows that $a_{1,p} = 0$ for all $p \neq 1$, giving just one non-zero term:
$$a_{1,1}^{(k+1)} = a_{1,1}\cdot a_{1,1}^{(k)} = 1.$$
Now, as you may have guessed, the second case is much trickier. But I would take a careful look at the implications of $(i,j)$ for the second case on the terms $a_{i,j}$ in the original matrix $A$. Pay close attention to the observation made by @Demophilus while doing this. It's painful to analyze the constraints on these terms, but you can directly use $(2 \leq i \leq j) \wedge (k+i>j)$ to immediately deduce that all but a couple of the $a_{i,p} =0$. Isolate these terms, figure out which $a_{p,j}^{(k)}$ stand out with them, and the binomial hint will come in handy. 
Regarding the last case--"else"--it's a bit tedious, and there are a few sub-cases to consider, but it's mostly straightforward. It's especially direct and clear to approach once you've figured out the second case, so I highly recommend figuring out that one first. 
A: Note that for fixed $t$, the matrix element $a_{t,p}$ is non-zero for very few $p$, only for two values of $p$ in fact. So the sum you have reduces to two terms, for which it becomes easier to evaluate $a^{(k)}_{p,s}$.
