Let $A$ be a matrix sized $p\times p$, where $2\le p$. Using recurrence relations, describe $A^k$. Let $A$ be a matrix sized $p\times p$, Where $2\le p$.
The matrix values in the main diagonal are $0$ and the rest are $1$'s. 
Example for $A$ where $p=5$:
$$\begin{bmatrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \\ \end{bmatrix}
$$
Using reccurences relations, describe $A^k$.
 A: HINT: Calculating a few powers of such matrices quickly suggests that $A^k$ always has just two distinct entries, one appearing on the diagonal, and the other appearing off the diagonal. You might try proving this by induction: the induction step, if it works, is likely to tell you what the recurrences actually are. 
Let the $(i,j)$-entry of $A^k$ be $a_{ij}^k$, and suppose that $a_{ii}^k=b_k$ for $i=1,\dots,n$ and $a_{ij}^k=c_k$ when $i\ne j$. Then
$$a_{ii}^{k+1}=\sum_{j=1}^{i-1}c_k+\sum_{j=i+1}^nc_k=(n-1)c_k\;;$$
why? This is independent of $i$, so all of the diagonal entries of $A^{k+1}$ are equal to $b_{k+1}(n-1)c_k$. See if you can finish it by dealing with the off-diagonal elements.
A: Let $B$ be the matrix with all entries equal to $1$. Then $B^n=p^{n-1}B$ for $n\geq1$. We have $A=B-I$. So
$$
A^n=(B-I)^n=(-1)^nI+\sum_{k=1}^n\,{n\choose k}\,B^k\,(-1)^{n-k}=(-1)^nI+\sum_{k=1}^n\,{n\choose k}\,p^{k-1}B\,(-1)^{n-k}\\
=(-1)^nI+B\,\sum_{k=1}^n\,{n\choose k}\,p^{k-1}\,(-1)^{n-k}=(-1)^nI+B\,\frac1p\,\sum_{k=1}^n\,{n\choose k}\,p^{k}\,(-1)^{n-k}\\
=(-1)^nI+B\,\frac1p\,[(p-1)^n-(-1)^n].
$$
Using that $B=A+I$, we get
$$
A^n=(-1)^nI+\frac1p\,[(p-1)^n-(-1)^n]\,(A+I).
$$
