I am attempting to solve the following problem, but I'm confused on a solution that is offered for it.
The question asks "Let $S$ $=$ {$P_1,..., P_n$} be a family of polynomials such that for all $i,j \leq n$ : $\deg(P_i) \not = \deg(P_j)$. Show that $S$ is linearly independent".
The solution offered states the following :
"We will prove this by induction on n, where n is the number of polynomials.
Base case: Let $n=1$. Then $S = {P_1}$ and since a set containing only one nonzero vector is linearly independent, the desired condition holds.
Inductive Step: Assume that $S = {P_1, ... P_n}$ is linearly independent. Consider the case when $S' = {P_1, ..., P_n, P_{n+1}}$ and $\deg(P_i) \not = \deg(P_j)$ for all $i \not = j$. Consider $a_1P_1 + ... + a_nP_n + a_{n+1}P_{n+1} = 0$. Define $P_k$ to be the polynomial of highest degree. It must be true that
$a_1P_1 + \space ... \space + a_{k-1}P_{k-1} + a_{k+1}P_{k+1} +\space ... \space + a_nP_n + a_{n+1}P_{n+1} = a_kP_k $.
If $a_k \not=0$, then right hand side of the preceding equation has the same degree as $P_k$ while the left hand side has degree strictly less than $P_k$ and this is a contradiction. It must follow that $a_k = 0$."
This is the part where I get confused. Why must this be a contradiction? If we say that $P_k$ is the polynomial of highest degree, isn't it impossible for any other polynomial to have a degree higher than $P_k$ or equal to $P_k$ due to our conditions?
Thanks!!