Let $A,B \in \mathcal{M}_n(\mathbf{C})$. Let us consider the following assertions :
(i) $\forall k \in [[ 1,n ]]$, $\mathrm{Tr}(A^k) = \mathrm{Tr}(B^k)$
(ii) $\forall k \in \mathbf{N}$, $\mathrm{Tr}(A^k) = \mathrm{Tr}(B^k)$
(iii) $P_A = P_B$ where $P_A$ is the characteristic polynomial of $A$
I want to prove (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) in this order. For the implication (i) $\Rightarrow$ (ii) I am looking for a proof without using Newton's identities (which would directly prove (i) $\Rightarrow$ (iii)).
For (ii) $\Rightarrow$ (iii) I think I have a proof.
Let $\mathrm{Sp}(A) \cup \mathrm{Sp}(B) = \{\lambda_1,\ldots,\lambda_p\}$ with $\lambda_i$ are all different. Let $m_i$ the multiplicity of $\lambda_i$ in $P_A$ and $n_i$ the multiplicity of $\lambda_i$ in $P_B$. (If $\lambda_i \notin \mathrm{Sp}(A)$ then $m_i=0$.)
$(i)$ is equivalent to $\sum_{i=1}^p (n_i-m_i) \lambda_i^k = 0$ for all $k \in \mathbf{N}$. If we take only the $p-1$ first equations, we have a Cramer linear system because the determinant of this system is a Vandermonde determinant which is non-null. The only solution is the trivial one which implies that $n_i-m_i=0$ so $n_i=m_i$. We can conclude that $\mathrm{Sp}(A) = \mathrm{Sp}(B)$ and all eigenvalues have the same multiplicity and therefore $P_A=P_B$.