Results 1 to 7 of 7

Math Help - Induction proof

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    23

    Induction proof

    I'm just trying to learn induction from scratch and my book asks me to proof the generalized version of the triangle inequality.

    If a_{1},a_{2},...,a_{n} are arbitrary real numbers, then

    |a_{1}+a_{2}+ ...+a_{n}|\leq |a_{1}| + |a_{2}| +...+ |a_{n}|.

    My solution is as follows
    :
    Let P_{n} be the preposition that |a_{1}+a_{2}+ ...+a_{n}|\leq |a_{1}| + |a_{2}| +...+ |a_{n}|.

    P_{1} and P_{2} are true. P_{2} is the normal triangle inequality, so i assume i don't need to show that it is true.

    With the induction hypothesis i assume that P_{n} is true.

    Setting
    |a_{1}+a_{2}+ ...+a_{n}| = S_{1}
     |a_{1}| + |a_{2}| +...+ |a_{n}|= S_{2}
    |S_{1}| \leq S_{2}
    So

    We are trying to show that
    |S_{1} +a_{n+1}| \leq |S_{2}| + |a_{n+1}|

    Using cases
    1) S_{1} \geq 0 and  a_{n+1} \geq 0

     |S_{1} +a_{n+1}|= S_{1} +a_{n+1} \leq S_{2} +a_{n+1} this is true because |S_{1}| \leq S_{2} according to the induction hypothesis. Also according to the transitive property of real numbers if a< b, then a+c < b+c.

    2) S_{1} < 0 and a_{n+1} \geq 0

    |S_{1} +a_{n+1}| \leq S_{2} +|a_{n+1}|

    Since |S_{1}| \leq S_{2} is true then |S_{1} +a_{n+1}| \leq |S_{1}| + |a_{n+1}| \leq  S_{2} +|a_{n+1}|<br />

    3 S_{1} < 0 and  a_{n+1} < 0

    |S_{1} +a_{n+1}| \leq|S_{1} |+|a_{n+1}|\leq S_{2} +|a_{n+1}|

    Therefore it is true that |a_{1}+a_{2}+ ...+a_{n}|\leq |a_{1}| + |a_{2}| +...+ |a_{n}|.


    Is my proof correct ?
    And is there a better way of doing this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    ynj
    ynj is offline
    Senior Member
    Joined
    Jul 2009
    Posts
    254
    n=2
    (|a1|+|a2|)^2=a1^2+a2^2+2|a1||a2|>=a1^2+a2^2+2a1a2 =(a1+a2)^2
    thus |a1+a2|<=|a1|+|a2|
    suppose for k<n it is true
    then
    |a1+....an|<=|a1+....an-1|+|an|
    by induction |a1+...an-1|<=|a1|+...|an-1|
    so |a1+...an|<=|a1|+..|an|
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2009
    Posts
    23

    Another one- Can someone help me check this

    If a_{i}\geq 0 and i \geq 1 then

    (1+a_{1})(1+a_{2})\cdot \cdot \cdot(1+a_{n}) \geq 1+a_{1} + a_{2}+...+ a_{n}

    My solution:

    Let P_{n} = (1+a_{1})(1+a_{2})\cdot \cdot \cdot(1+a_{n}) \geq 1+a_{1} + a_{2}+...+ a_{n}<br />
ofcourse P_{1} and P_{2} are true.

    According to the induction hypothesis, we assume P_{n} is true.

    Let (1+a_{1})(1+a_{2})\cdot \cdot \cdot(1+a_{n})= \rho

    and
    1+a_{1} + a_{2}+...+ a_{n} = S

    We have \rho \geq S

    Okay moving on ...

    We have to show this is true and  P_{n} implies P_{n+1}
    \rho \cdot(1+ a_{n+1} )\geq S + a_{n+1}

    Doing some algebra we get

    \rho \geq S + a_{n+1}(1-\rho) which is true because (1-\rho)\leq 0 and \rho \geq S and  a_{n+1}\geq 0

    Is this proof correct and is there a more clever way of doing this É



    Quote Originally Posted by ynj View Post
    n=2
    (|a1|+|a2|)^2=a1^2+a2^2+2|a1||a2|>=a1^2+a2^2+2a1a2 =(a1+a2)^2
    thus |a1+a2|<=|a1|+|a2|
    suppose for k<n it is true
    then
    |a1+....an|<=|a1+....an-1|+|an|
    by induction |a1+...an-1|<=|a1|+...|an-1|
    so |a1+...an|<=|a1|+..|an|

    Thanks a lot this is a more clever way of doing it. Thanks again.


    But is my way correct É ( My keyboard is acting up)
    Last edited by justchillin; August 14th 2009 at 08:46 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    ynj
    ynj is offline
    Senior Member
    Joined
    Jul 2009
    Posts
    254
    Quote Originally Posted by justchillin View Post
    I'm just trying to learn induction from scratch and my book asks me to proof the generalized version of the triangle inequality.

    If a_{1},a_{2},...,a_{n} are arbitrary real numbers, then

    |a_{1}+a_{2}+ ...+a_{n}|\leq |a_{1}| + |a_{2}| +...+ |a_{n}|.

    My solution is as follows:
    Let P_{n} be the preposition that |a_{1}+a_{2}+ ...+a_{n}|\leq |a_{1}| + |a_{2}| +...+ |a_{n}|.

    P_{1} and P_{2} are true. P_{2} is the normal triangle inequality, so i assume i don't need to show that it is true.

    With the induction hypothesis i assume that P_{n} is true.

    Setting
    |a_{1}+a_{2}+ ...+a_{n}| = S_{1}
     |a_{1}| + |a_{2}| +...+ |a_{n}|= S_{2}
    |S_{1}| \leq S_{2}
    So

    We are trying to show that
    |S_{1} +a_{n+1}| \leq |S_{2}| + |a_{n+1}|

    Using cases
    1) S_{1} \geq 0 and  a_{n+1} \geq 0

     |S_{1} +a_{n+1}|= S_{1} +a_{n+1} \leq S_{2} +a_{n+1} this is true because |S_{1}| \leq S_{2} according to the induction hypothesis. Also according to the transitive property of real numbers if a< b, then a+c < b+c.

    2) S_{1} < 0 and a_{n+1} \geq 0

    |S_{1} +a_{n+1}| \leq S_{2} +|a_{n+1}|

    Since |S_{1}| \leq S_{2} is true then |S_{1} +a_{n+1}| \leq |S_{1}| + |a_{n+1}| \leq S_{2} +|a_{n+1}|<br />

    3 S_{1} < 0 and  a_{n+1} < 0

    |S_{1} +a_{n+1}| \leq|S_{1} |+|a_{n+1}|\leq S_{2} +|a_{n+1}|

    Therefore it is true that |a_{1}+a_{2}+ ...+a_{n}|\leq |a_{1}| + |a_{2}| +...+ |a_{n}|.


    Is my proof correct ?
    And is there a better way of doing this?
    I think it is correct..
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2009
    Posts
    23
    What about the second one É ( my keyboard doesnèt want to produce punnctuations.)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    ynj
    ynj is offline
    Senior Member
    Joined
    Jul 2009
    Posts
    254
    Quote Originally Posted by justchillin View Post
    If a_{i}\geq 0 and i \geq 1 then

    (1+a_{1})(1+a_{2})\cdot \cdot \cdot(1+a_{n}) \geq 1+a_{1} + a_{2}+...+ a_{n}

    My solution:

    Let P_{n} = (1+a_{1})(1+a_{2})\cdot \cdot \cdot(1+a_{n}) \geq 1+a_{1} + a_{2}+...+ a_{n}<br />
ofcourse P_{1} and P_{2} are true.

    According to the induction hypothesis, we assume P_{n} is true.

    Let (1+a_{1})(1+a_{2})\cdot \cdot \cdot(1+a_{n})= \rho

    and
    1+a_{1} + a_{2}+...+ a_{n} = S

    We have \rho \geq S

    Okay moving on ...

    We have to show this is true and  P_{n} implies P_{n+1}
    \rho \cdot(1+ a_{n+1} )\geq S + a_{n+1}

    Doing some algebra we get

    \rho \geq S + a_{n+1}(1-\rho) which is true because (1-\rho)\geq 0 and \rho \geq S and  a_{n+1}\geq 0

    Is this proof correct and is there a more clever way of doing this É






    Thanks a lot this is a more clever way of doing it. Thanks again.


    But is my way correct É ( My keyboard is acting up)
    I think it is correct...I think it will be simple enough......
    Actually, induction is not necessary. You can prove it just by multiplying the left side,(1+a1)...(1+an)=1+a1+...an+T,where obviously T>0
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    May 2009
    Posts
    23
    Okay thanks.

    If anyone has any other suggestions or thinks what i did is too elaborate or wrong please feel free to let me know.


    Btw i did make a mistake i said (1-\rho) \geq 0 which is false it should have been (1-\rho)\leq 0.
    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, 07:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 12:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum