1. ## Induction over n

I hope this is the right subforum: the question stems from this other thread:
Induction of linear independent vectors

Use induction over $\displaystyle n$ to prove that for any field elements $\displaystyle c, x_k$:

$\displaystyle c \left(\sum_{k=1} ^n x_k \right) = \sum_{k=1} ^n c x_k$
Ok, so there's nothing special about the formula.

i) $\displaystyle c \left(\sum_{k=1} ^1 x_1 \right) = \sum_{k=1} ^1 c x_1 = c x_1$

ii) but then... ?
$\displaystyle c \left(\sum_{k=1} ^n x_n \right) = \sum_{k=1} ^n c x_n = c x_1 + c x_2 + c x_3 + ... + c x_n$

I mean... what am I showing here, exactly, $\displaystyle P(n-1) \Rightarrow P(n)$?
$\displaystyle c \left(\sum_{k=1} ^n x_n \right) = \sum_{k=1} ^{n-1} c x_{n-1} + c x_n$

Does this work?
I'm a bit confused about the inductive step in this kind of problem. It seems kind of obvious and I guess it's really just an example of the distributive law?

2. Hi bmp05.

Originally Posted by bmp05
ii) but then... ?
$\displaystyle c \left(\sum_{k=1} ^n x_n \right) = \sum_{k=1} ^n c x_n = c x_1 + c x_2 + c x_3 + ... + c x_n$

I mean... what am I showing here, exactly, $\displaystyle P(n-1) \Rightarrow P(n)$?
$\displaystyle c \left(\sum_{k=1} ^n x_n \right) = \sum_{k=1} ^{n-1} c x_{n-1} + c x_n$
For the inductive step, you assume that

$\displaystyle c \left(\sum_{k=1} ^n x_n \right) = \sum_{k=1} ^n c x_n\quad\ldots\,\fbox1$

is true, then you try and prove that $\displaystyle c \left(\sum_{k=1} ^{n+1} x_n \right) = \sum_{k=1} ^{n+1} c x_n$ is also true. Can you do that?

Hint: Add $\displaystyle cx_{n+1}$ to both sides of $\displaystyle \fbox1.$

3. Hmmm... thanks Abstractionist. That's straight-forward enough:

$\displaystyle c \left(\sum_{k=1} ^n x_n \right) = \sum_{k=1} ^n c x_n$

$\displaystyle c \left(\sum_{k=1} ^{n+1} x_n \right) + cx_{n+1} = c (x_1 + x_2 + x_3 + \ldots + x_n + x_{n+1}) = cx_1 + cx_2 + cx_3 + \ldots + cx_n + cx_{n+1}$

$\displaystyle \sum_{k=1} ^{n+1} c x_n = cx_1 + cx_2 + cx_3 + \ldots + cx_n + cx_{n+1}$

$\displaystyle \sum_{k=1} ^{n+1} c x_n = c \left(\sum_{k=1} ^n x_n \right) + cx_{n+1}$
--

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, there is a set $\displaystyle V = \{v_1, v_2, v_3, \ldots , v_n\}$

$\displaystyle w_1 = \sum_{k=1} ^{1} v_k = v_1 \in V$

induction hypothesis is
$\displaystyle w_i = \sum_{k=1} ^{i} v_k, i \in \mathbb{N}$ but there are only $\displaystyle n$ vectors in $\displaystyle V$?

4. I think I understand now, the elements that make up $\displaystyle w_i$ are all subsets of $\displaystyle V^n$.

5. $\displaystyle V$ is the set of linearly independent vectors $\displaystyle V = \{v_1, v_2, v_3, \ldots , v_n\}$
The set $\displaystyle W = \{w_1, w_2, w_3, \ldots , w_n\}$
$\displaystyle w_1 = v_1 \in V$ and trivially linear independent as only vector in space.
$\displaystyle w_2 = v_1 + v_2$
$\displaystyle w_3 = v_1 + v_2 + v_3$

So, the question is how to show that the vectors in $\displaystyle W$ are linearly independent? It's easy to see, because the matrix formed by n linear equations is a lower triangle, which row reduces to $\displaystyle I_n$. The subspace $\displaystyle W$ is going to have dimension $\displaystyle n$ and therefore $\displaystyle w_i \in W$ is linearly independent? But anyway, this has to be shown using induction?

6. $\displaystyle w_n = \beta_1 (v_1) + \beta_2 (v_1 + v_2) + \beta_3 (v_1 + v_2 + v_3) + \ldots + \beta_n (v_1 + v_2 + v_3 + \ldots + v_n)$
and $\displaystyle w_n$ is linearly independent iff $\displaystyle \beta_{1 ... n} = 0$ is the only solution to the combination of the vectors $\displaystyle w_1 ... w_n$.

So, a combination of any of the vectors in $\displaystyle V$ is never 0, by definition of their being linearly independent therefore the only combination of the vectors in $\displaystyle W$ that give zero is when $\displaystyle \beta_{1 \ldots n} = 0$.

But I need help with the induction.

7. $\displaystyle w_n = \sum_{k=1} ^{n} v_k, n \in \mathbb{N}$

$\displaystyle \sum_{k=1} ^n \alpha_k v_k = 0, k, n \in \mathbb{N}, \alpha \in \mathbb{F}$
$\displaystyle = \alpha \sum_{k=1} ^n v_k = 0, k, n \in \mathbb{N}, \alpha = 0$ given, because $\displaystyle V$ is linearly independent.

but also:
$\displaystyle \sum_{k=1} ^n \beta_k \left(\alpha \sum_{k=1} ^n v_k \right) = 0, k, n \in \mathbb{N}, \alpha = 0, \beta \in \mathbb{F}$

$\displaystyle = \alpha \sum_{k=1} ^n \beta_k \left( \sum_{k=1} ^n v_k \right) = 0, k, n \in \mathbb{N}, \alpha = 0, \beta \in \mathbb{F}$

$\displaystyle = \gamma \left( \sum_{k=1} ^n v_k \right) = 0, k, n \in \mathbb{N}, \gamma = 0$

...something has gone wrong, I suspect- and still no induction.