Results 1 to 3 of 3

Math Help - Mathematical induction problems

  1. #1
    Newbie
    Joined
    Nov 2007
    Posts
    7

    Mathematical induction problems

    I'm left with these problems to do if anyone can help with any or all of them. Could you while helping me solve the problems try to explain in details especially with the proofs as this is one of my weaker sections in discrete maths. Thanks in advance.

    1) Prove by mathematical induction that all positive integers n,

    a)1*2+2*3+3*4...n(n+1)=n(n+1)(n+2)/3
    b)1/(1*3)+1/(3*5)+1/(5*7)+...+1/(2n-1)(2n+1)=n/2n+1
    c)(5^2n)-1 is divisible by 24
    d) 1^2-2^2+3^2...((-1)^n+1)n^2=((-1)^n+1)n(n+1))/2

    2) Prove by mathematical induction
    a) that 2n+1<=2^n for n=3,4,...
    b)Use part (a) in the proof that 2^n>=n^2 for n=4,5,...

    3) Use mathematical induction to show that postage of 5 cents or more can be achieved by using only 2 cents and 5 cent stamps(as many of each is needed.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,746
    Thanks
    648
    Hello, aloufy!

    I will assume you already know the basics of Induction.
    I'll do a few of these . . .


    Prove by mathematical induction:

    a)\;\;1\cdot2+2\cdot3+3\cdot4 + \cdots + n(n+1) \;=\;\frac{n(n+1)(n+2)}{3}
    Verify S(1)\!:\;\;1\cdot2 \:=\:\frac{1\cdot2\cdot3}{3}\quad\Rightarrow\quad 2\:=\:2 . . . true!

    Assume S(k)\!:\;\;1\cdot2 + 2\cdot3 + 3\cdot 4 + \cdots + k(k+1)\;=\;\frac{k(k+1)(k+2)}{3}


    Add (k+1)(k+2) to both sides:
    . . 1\cdot2\,+\,2\cdot 3\,+\,\cdots +\,k(k+1) {\color{blue}\,+\,(k+1)(k+2)} \;=\;\frac{k(k+1)(k+2)}{3}{\color{blue}\,+\,(k+1)(  k+2)}

    On the right side, factor: . ((k+1)(k+2)\left[\frac{k}{3} + 1\right] \;=\;(k+1)(k+2)\left(\frac{k+3}{3}\right)

    And we have:
    . . 1\cdot2 + 2\cdot 3 + 3\cdot4 + \cdots + (k+1)(k+2) \;=\;\frac{(k+1)(k+2)(k+3)}{3}

    And we shown that S(k+1) is true.
    . . The inductive proof is compete.




    c)\;\;5^{2n} -1 is divisible by 24

    Verify S(1)\!:\;\;5^2-1 \:=\:24 . . . True!

    Assume S(k)\!:\;\;5^{2k} - 1 \:=\:24a for some integer a.


    Add 24\cdot5^{2k} to both sides: . 5^{2k}\,{\color{blue}+\,24\cdot5^{2k}}-1\;=\;24a\,{\color{blue}+\,24\cdot5^{2k}}

    . . The left side is: . 5^{2k}[1 + 24] - 1 \;=\;5^{2k}\cdot25 - 1 \;=\;5^{2k}\cdot5^2 - 1 \;=\;5^{2k+2} - 1\;=\;5^{2(k+1)} - 1

    . . The right side is: . 24a + 24\cdot5^{2k} \;=\;24(a + 5^{2k})

    \text{Hence we have: }\;5^{2(k+1)} - 1 \;=\;\underbrace{24\left(a + 5^{2k}\right)}_{\text{multiple of 24}}

    Therefore, we have proved S(k+1).
    . . The inductive proof is complete.

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2007
    Posts
    7
    Quote Originally Posted by Soroban View Post
    Hello, aloufy!

    I will assume you already know the basics of Induction.
    I'll do a few of these . . .


    Verify S(1)\!:\;\;1\cdot2 \:=\:\frac{1\cdot2\cdot3}{3}\quad\Rightarrow\quad 2\:=\:2 . . . true!

    Assume S(k)\!:\;\;1\cdot2 + 2\cdot3 + 3\cdot 4 + \cdots + k(k+1)\;=\;\frac{k(k+1)(k+2)}{3}


    Add (k+1)(k+2) to both sides:
    . . 1\cdot2\,+\,2\cdot 3\,+\,\cdots +\,k(k+1) {\color{blue}\,+\,(k+1)(k+2)} \;=\;\frac{k(k+1)(k+2)}{3}{\color{blue}\,+\,(k+1)(  k+2)}

    On the right side, factor: . ((k+1)(k+2)\left[\frac{k}{3} + 1\right] \;=\;(k+1)(k+2)\left(\frac{k+3}{3}\right)

    And we have:
    . . 1\cdot2 + 2\cdot 3 + 3\cdot4 + \cdots + (k+1)(k+2) \;=\;\frac{(k+1)(k+2)(k+3)}{3}

    And we shown that S(k+1) is true.
    . . The inductive proof is compete.





    Verify S(1)\!:\;\;5^2-1 \:=\:24 . . . True!

    Assume S(k)\!:\;\;5^{2k} - 1 \:=\:24a for some integer a.


    Add 24\cdot5^{2k} to both sides: . 5^{2k}\,{\color{blue}+\,24\cdot5^{2k}}-1\;=\;24a\,{\color{blue}+\,24\cdot5^{2k}}

    . . The left side is: . 5^{2k}[1 + 24] - 1 \;=\;5^{2k}\cdot25 - 1 \;=\;5^{2k}\cdot5^2 - 1 \;=\;5^{2k+2} - 1\;=\;5^{2(k+1)} - 1

    . . The right side is: . 24a + 24\cdot5^{2k} \;=\;24(a + 5^{2k})

    \text{Hence we have: }\;5^{2(k+1)} - 1 \;=\;\underbrace{24\left(a + 5^{2k}\right)}_{\text{multiple of 24}}

    Therefore, we have proved S(k+1).
    . . The inductive proof is complete.

    Thanks Soroban "big help"...Can anyone help me with the other problems?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Four mathematical induction problems
    Posted in the Algebra Forum
    Replies: 5
    Last Post: November 3rd 2010, 03:17 PM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. mathematical induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 1st 2010, 03:48 PM
  4. Some help on mathematical induction?
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 30th 2009, 02:34 AM
  5. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 1st 2009, 11:57 AM

Search Tags


/mathhelpforum @mathhelpforum