Results 1 to 6 of 6

Math Help - proof by induction

  1. #1
    Junior Member
    Joined
    Jan 2009
    Posts
    46

    Post proof by induction

    pls i need help to proof the following by induction technique



    (summation) from i=0 to n for x^i= [(1-x^(n+1)]/ [1-x]
    where x does not equal to 1
    first i substituted the letter i by a
    then i thought about adding 2 (since 1 is not accepted) by didnt go anywhere

    thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    Quote Originally Posted by alex83 View Post
    pls i need help to proof the following by induction technique



    (summation) from i=0 to n for x^i= [(1-x^(n+1)]/ [1-x]
    where x does not equal to 1
    first i substituted the letter i by a
    then i thought about adding 2 (since 1 is not accepted) by didnt go anywhere

    thank you
    P_k = \sum_{i=0}^{k} x^i = \frac{(1-x^{k+1})}{1-x}

    test P_1

    \sum_{i=0}^1 x^i = x^0 + x=1+x

    \frac{1 - x^{1+1}}{1-x} = 1+x

    P_1 is true

    suppose that P_k is true try P_{k+1} is true

    \sum_{i=0}^{k+1} x^i = x^{k+1}+\sum_{i=0}^{k} x^i

    but \sum _{i=0}^{k} x^k = \frac{1- x^{k+1}}{1-x}

    so

    \sum_{i=0}^{k+1} x^i = \frac{1- x^{k+1}}{1-x} + x^{k+1}

    \frac{1- x^{k+1}}{1-x} = \frac{1- x^{k+1} + x^{k+1} - x^{k+2}}{1-x} = \frac{1-x^{k+2}}{1-x}

    \sum_{i=0}^{k+1} x^i = \frac{1-x^{k+2}}{1-x}

    so P_{k+1} is true the proof end
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244
    Quote Originally Posted by alex83 View Post
    pls i need help to proof the following by induction technique



    (summation) from i=0 to n for x^i= [(1-x^(n+1)]/ [1-x]
    where x does not equal to 1
    first i substituted the letter i by a
    then i thought about adding 2 (since 1 is not accepted) by didnt go anywhere

    thank you
    Start this way: Let n=1, then for the LHS

    \sum_{i=0}^{1}x^{i}=x^{0}+x^{1}=1+x and for the RHS

     <br />
\frac{1-x^{\{1+1\}}}{1-x}=\frac{1-x^{2}}{1-x}=\frac{(1-x)(1+x)}{1-x}=1+x<br />
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jan 2009
    Posts
    46
    Quote Originally Posted by Amer View Post
    P_k = \sum_{i=0}^{k} x^i = \frac{(1-x^{k+1})}{1-x}

    test P_1

    \sum_{i=0}^1 x^i = x^0 + x=1+x

    \frac{1 - x^{1+1}}{1-x} = 1+x

    P_1 is true

    suppose that P_k is true try
    P_{k+1} is true

    \sum_{i=0}^{k+1} x^i = x^{k+1}+\sum_{i=0}^{k} x^i

    but \sum _{i=0}^{k} x^k = \frac{1- x^{k+1}}{1-x}

    so

    \sum_{i=0}^{k+1} x^i = \frac{1- x^{k+1}}{1-x} + x^{k+1}

    \frac{1- x^{k+1}}{1-x} = \frac{1- x^{k+1} + x^{k+1} - x^{k+2}}{1-x} = \frac{1-x^{k+2}}{1-x}

    \sum_{i=0}^{k+1} x^i = \frac{1-x^{k+2}}{1-x}

    so P_{k+1} is true the proof end
    thank you
    but the question has a condition that x does not equals to 1
    i thought we are not allowed to use the (1) in our assumption
    is this true
    thnx again
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by alex83 View Post
    pls i need help to proof the following by induction technique



    (summation) from i=0 to n for x^i= [(1-x^(n+1)]/ [1-x]
    where x does not equal to 1
    first i substituted the letter i by a
    then i thought about adding 2 (since 1 is not accepted) by didnt go anywhere

    thank you
    Hi alex83,

    P(k)

    \sum_{i=0}^kx^i=\frac{1-x^{k+1}}{1-x}

    P(k+1)

    \sum_{i=0}^{k+1}x^i=\frac{1-x^{k+2}}{1-x}

    Try to prove that P(k) being true causes P(k+1) to be true

    Proof

    \sum_{i=0}^{k+1}x^i=\sum_{i=0}^kx^i+x^{k+1}

    If P(k) is true, this will be \frac{1-x^{k+1}}{1-x}+x^{k+1}=\frac{1-x^{k+1}}{1-x}+\frac{(1-x)x^{k+1}}{1-x}

    =\frac{1-x^{k+1}+x^{k+1}-x^{k+2}}{1-x}=\frac{1-x^{k+2}}{1-x}

    Hence P(k) true causes P(k+1) to be true

    Therefore if the formula is valid for i=0, it's valid for i=1 and therefore for i=2,
    for i=3, for i=4, for i=5........ to infinity

    To check the validity for i=0

    x^0=1

    \frac{1-x^{0+1}}{1-x}=\frac{1-x}{1-x}=1

    Hence the hypothesis is valid for x not equal to 1
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by alex83 View Post
    thank you
    but the question has a condition that x does not equals to 1
    i thought we are not allowed to use the (1) in our assumption
    is this true
    thnx again
    Hi alex83,

    x cannot be 1 as 1-x in the denominator would be zero,
    and we need to avoid having a divide by zero.

    Choosing i=1 would be testing the formula for the first 2 terms in the sum,
    though you may start at i=0, which strictly speaking is more correct.
    If the sum was from i=1 to n, we test the formula for i=1,
    but since the sum starts at i=0, then i=0 gives the first term in the sum.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 08:22 AM
  2. Proof by induction help??
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 5th 2009, 02:19 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  5. Proof by induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 5th 2008, 05:11 AM

Search Tags


/mathhelpforum @mathhelpforum