Results 1 to 7 of 7

Thread: Induction over n

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    90

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Hi bmp05.

    Quote Originally Posted by bmp05 View Post
    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.$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2009
    Posts
    90
    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$?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2009
    Posts
    90
    I think I understand now, the elements that make up $\displaystyle w_i$ are all subsets of $\displaystyle V^n$.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Mar 2009
    Posts
    90
    $\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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Mar 2009
    Posts
    90
    $\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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Mar 2009
    Posts
    90
    $\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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: Apr 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Apr 19th 2010, 05:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 7th 2008, 04:10 PM

Search Tags


/mathhelpforum @mathhelpforum