Raising entries to $k$th power 
Let $A$ be an $n \times n$ real matrix, and define $A_k$ to be the matrix whose entires are $(a_{ij})^k$. Prove that if $A^k = A_k$ for $k = 1, \ldots, n + 1$, then $A^m = A_m$ for all $m$.

My attempt:

We prove by induction on induction on $m$. $m = 1$ is true by assumption. Suppose it's true for $m = 1, \ldots, n + 1$ . Considering $A^{n+2}$ and defining $X = A^{n+1} = A_{n+1}$, we have:
\begin{align*}
(A^{n+2})_{i,j} & = ((A^{n+1})A)_{ij} \\
& =  (XA)_{ij} \\
& = \sum\limits_{k=1}^n x_{ik} a_{kj} \\
& = \sum\limits_{k=1}^n (a_{ik})^n (a_{kj}) 
\end{align*}

How does this look?
 A: Hint: There is a polynomial $\phi_A$ (the characteristic polynomial of $A$) of degree $n$ such that $\phi_A(A)=0$. Also, for any polynomial $p$, you can divide $p$ by $\phi_A$ with remainder $r$ of degree $<n$ so that $p(X)=\phi_A(X)q(X)+r(X)$ (for some quotient $q$). This means that $p(A)=\phi_A(A)q(A)+r(A)=r(A)$.
In particular, you can take $p(X)=X^{m-1}$ and you can write $r(X)=\sum_{k=0}^{n-1}r_kX^k$. Now try three things:
(1) Prove that for any pair of indices $i,j$ you have $A_{ij}\phi_A(A_{ij})=0$. This should follow from $\phi_A(A)=0$ (which implies $A\phi_A(A)=0$) and the assumption given in the problem. If you need to, write the characteristic polynomial explicitly: $\phi_A(X)=\sum_{k=0}^{n}\phi_kX^k$.
(2) Prove that $(A^m)_{ij}=\sum_{k=0}^{n-1}r_k(A^{k+1})_{ij}=\sum_{k=0}^{n-1}r_k(A_{k+1})_{ij}$. This should follow from $A^m=A\cdot A^{m-1}=A(\phi_A(A)q(A)+r(A))=A\cdot r(A)$.
(3) Prove that $(A_m)_{ij}=\sum_{k=0}^{n-1}r_k(A_{k+1})_{ij}$ as well! This should follow from (1) above.
A: Using the minimal polynomial of $A$ or Cayley-Hamilton, we get some relation like
$$ A^n = \sum_{k < n} c_{k + 1} A^k. $$
If we multiply both sides by $A$ then all the powers of $A$ are between $1$ and $n + 1$ so we obtain also
$$ A^{n+1} = \sum_{k = 1}^n c_k A^k \quad \Longleftrightarrow \quad a_{i,j}^{n + 1} = \sum_{k = 1}^n c_k a_{i,j}^k$$
Now multiply both sides by $A$ again to get
\begin{align}
(A^{n + 2})_{i,j} &= \sum_{k = 1}^{n} c_k (A^{k + 1})_{i,j} \\ 
&= \sum_{k = 1}^{n} c_k a_{i,j}^{k+1} \\
&= a_{ij} \sum_{k = 1}^n c_k a_{i,j}^k \\
&= a_{ij} \cdot a_{ij}^{n + 1} = a_{ij}^{n + 2}.
\end{align}
And you can write this induction step more generally.
