How do I prove that the trace of a matrix to its $k$th power is equal to the sum of its eigenvalues raised to the $k$th power?

1. $tr(A)=\sum \lambda_i$
2. If $\lambda_i$ is eigenvalue of $A$, then $\lambda_i^k$ is eigenvalue of $A^k$. This mapping preserves multiplicities.

The first one is a classic result, easily deduced from the characteristic polynomial. The second one is a little trickier (if there are repeated eigenvalues).

Sum of roots of a polynomial is given by $-\frac{b}{a}$, if the polynomial looks like $a\lambda^N+b\lambda^{N-1}+\dots$. Now, eigenvalues are roots of polynomial $\det(A-\lambda I)$. Try to prove that $-\frac{b}{a}$ in this case is $\mathrm{trace}(A)$. See that $A^kv=A^{k-1}(Av)=A^{k-1}(\lambda_i v)=\lambda_i^k v$ (where $\lambda$ is a eigenvalue). Thus $\lambda_i^k$ are eigenvalues of $A^k$. Thus $\lambda_i^k$ are roots of polynomial $\det (A^k-\lambda I)$. Thus, their sum should equal $\mathrm{trace}(A^k)$.