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 $n$ to prove that for any field elements $c, x_k$:

$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) $c \left(\sum_{k=1} ^1 x_1 \right) = \sum_{k=1} ^1 c x_1 = c x_1$

ii) but then... ?
$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, $P(n-1) \Rightarrow P(n)$?
$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... ?
$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, $P(n-1) \Rightarrow P(n)$?
$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

$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 $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 $cx_{n+1}$ to both sides of $\fbox1.$

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

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

$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}$

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

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

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

So, there is a set $V = \{v_1, v_2, v_3, \ldots , v_n\}$

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

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

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

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

So, the question is how to show that the vectors in $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 $I_n$. The subspace $W$ is going to have dimension $n$ and therefore $w_i \in W$ is linearly independent? But anyway, this has to be shown using induction?

6. $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 $w_n$ is linearly independent iff $\beta_{1 ... n} = 0$ is the only solution to the combination of the vectors $w_1 ... w_n$.

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

But I need help with the induction.

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

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

but also:
$\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}$

$= \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}$

$= \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.