# Proving a family of polynomials is linearly independent

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!!

• You forgot to mention two things in the question/exercise. – Friedrich Philipp Mar 15 '16 at 1:49
• @FriedrichPhilipp I didn't type out the rest of the proof because I understand how the rest follows, but I don't understand that particular statement. – King Tut Mar 15 '16 at 1:51
• I meant the question in the beginning... – Friedrich Philipp Mar 15 '16 at 1:52
• "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?" Exactly. And exactly this is used here. The left hand side must have smaller degree then the right hand side. But then, of course, they cannot be equal. – Friedrich Philipp Mar 15 '16 at 1:57
• No problem. "Oh are you saying that it should be specified that all $P_k$'s are nonzero?" Of course. This is also used in the proof. Moreover, $deg(P_i)\neq deg(P_j)$ must be assumed to hold for $i\neq j$. – Friedrich Philipp Mar 15 '16 at 2:27