# Induction of linear independent vectors

• May 23rd 2009, 04:12 AM
bmp05
Induction of linear independent vectors
This is perhaps an easy question- more of a question about mathematical induction than linear algebra, perhaps:

Let $\displaystyle V$ be a vector-space over a field $\displaystyle \mathbb{F}$; $\displaystyle v_1,...,v_n$ are linear independent vectors in $\displaystyle V$. Prove by induction that the vectors $\displaystyle w_i = \sum_{k=1} ^{i} v_k, 1 \leq i \leq n$, are linear independent.

So, the question is asking to prove that the sum of linearly independent vectors is a vector which is linearly independent.

The condition for linear independence is:
$\displaystyle \sum_{k=1} ^{i} a_k v_k = 0, 1 \leq i \leq n$, when and only when $\displaystyle a_i = 0$ for all $\displaystyle 1 \leq i \leq k$

So $\displaystyle v_1 = a_1v_1 = 0 = a_1w_1$, but how do you make an induction step out of this? For $\displaystyle w_2$, the proposition is that $\displaystyle v_1 + v_2$ is also linearly independent:

$\displaystyle w_2 = v_1 + v_2 = a_1v_1 + a_2v_2 ; a_1=a_2=0$, so you can bracket the scalars out... hmm? But I still can't see how you can make an induction step. I'm sure it's kind of easy, but that's only making it more frustrating.
• May 23rd 2009, 04:36 AM
bmp05
Could you use the unit-vectors to prove this, or perhaps the dimension of the vector space? dim(V) = n?
• May 23rd 2009, 05:00 AM
NonCommAlg
Quote:

Originally Posted by bmp05
This is perhaps an easy question- more of a question about mathematical induction than linear algebra, perhaps:

Let $\displaystyle V$ be a vector-space over a field $\displaystyle \mathbb{F}$; $\displaystyle v_1,...,v_n$ are linear independent vectors in $\displaystyle V$. Prove by induction that the vectors $\displaystyle w_i = \sum_{k=1} ^{i} v_k, 1 \leq i \leq n$, are linear independent.

So, the question is asking to prove that the sum of linearly independent vectors is a vector which is linearly independent.

The condition for linear independence is:
$\displaystyle \sum_{k=1} ^{i} a_k v_k = 0, 1 \leq i \leq n$, when and only when $\displaystyle a_i = 0$ for all $\displaystyle 1 \leq i \leq k$

So $\displaystyle v_1 = a_1v_1 = 0 = a_1w_1$, but how do you make an induction step out of this? For $\displaystyle w_2$, the proposition is that $\displaystyle v_1 + v_2$ is also linearly independent:

$\displaystyle w_2 = v_1 + v_2 = a_1v_1 + a_2v_2 ; a_1=a_2=0$, so you can bracket the scalars out... hmm? But I still can't see how you can make an induction step. I'm sure it's kind of easy, but that's only making it more frustrating.

the induction is over $\displaystyle n,$ the number of vectors. for n = 1, there's nothing to prove. suppose the claim is true for n (induction hypothesis) and take any n + 1 linearly independent vectors

$\displaystyle v_1, \cdots , v_{n+1}.$ suppose $\displaystyle c_1v_1 + c_2(v_1+v_2) + \cdots + c_n(v_1 + \cdots + v_n) + c_{n+1}(v_1 + \cdots + v_{n+1})=0.$ if we show that $\displaystyle c_1=c_2 = \cdots = c_{n+1}=0,$ we're done. first note that if $\displaystyle c_{n+1}=0,$ then

$\displaystyle c_1=c_2 = \cdots = c_n = 0$ by induction hypothesis and so we're done. if $\displaystyle c_{n+1} \neq 0,$ then we'll have: $\displaystyle v_{n+1} = -c_{n+1}^{-1}c_1v_1 - c_{n+1}^{-1}c_2(v_1 + v_2) - \cdots - c_{n+1}^{-1}(c_n + c_{n+1})(v_1 + \cdots + v_n),$ which is not

possible because $\displaystyle v_1, \cdots , v_{n+1}$ are linearly independent. this completes our induction.
• May 23rd 2009, 10:40 AM
bmp05
So, you're proving the proposition for all of n- per definition- and then you prove it for n+1? But once again, this relies on the definition of linear independence. It's a strange question, I think. But thanks for your help NCA- btw. can you recommend a good text book for a first course in linear algebra?