Results 1 to 7 of 7

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

  3. #3
    Member
    Joined
    Mar 2009
    Posts
    90
    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?
    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 w_i are all subsets of V^n.
    Follow Math Help Forum on Facebook and Google+

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

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

  7. #7
    Member
    Joined
    Mar 2009
    Posts
    90
    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.
    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: April 21st 2011, 01:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 06:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2008, 05:10 PM

Search Tags


/mathhelpforum @mathhelpforum