Results 1 to 10 of 10

Math Help - Mathematical Induction

  1. #1
    Newbie
    Joined
    Aug 2007
    Posts
    9

    Mathematical Induction

    Mathematical Induction

    Gday im currently working on a Math C assignment it consists of determining a formula for a rectangular Patten of tiles, then proving it by mathematical induction the formula is:

    2n-2n+1

    However no mater how hard I try I cant work out how to prove it. Any help would be much appreciated

    thanks Quill
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,857
    Thanks
    321
    Awards
    1
    Quote Originally Posted by Quill View Post
    Mathematical Induction

    Gday im currently working on a Math C assignment it consists of determining a formula for a rectangular Patten of tiles, then proving it by mathematical induction the formula is:

    2n-2n+1

    However no mater how hard I try I cant work out how to prove it. Any help would be much appreciated

    thanks Quill
    This is going to be awfully hard to help you with unless you explain what that formula is supposed to refer to...

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2007
    Posts
    9
    thanks Dan These are the Questions

    Question 1
    By considering the tile patterns shown and other patterns in this design, determine a formula for the number of tiles in the nth pattern.



    (the colour has nothing to do with the patten just shoes each square)


    Question 2
    Prove the formula you obtained for the nth pattern.

    The answer i got for Question one is 2n-2n+1 i got it by dividing the patterns up in to equal proportions



    then i worked out each section like a rectangle (n x (n-1))/2
    multiplied that by 4 to account for each section then added 1 for the center one. it ended up like this:
    ((n x (n-1))/2) x 4 + 1
    then with a little rearrangement it became
    2n-2n+1
    its just Question 2 i don't understand how to do.
    Last edited by Quill; August 2nd 2007 at 04:10 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Here is a solution using a recursive function.
    Define S_1 = 1 and for n \ge 1 we get S_{n+1} = S_{n} + 4n, where S_n is the number of rectangles in each pattern.

    To see how this works, consider what we may call the main line. The number of rectangles this main line is 1,3,5,\cdots,2n-1. We a to add 2 rectangles, one above and one below, each of the rectangles on the main line plus one on each end.
    Thus S_{n+1} = S_{n} + 2(2n-1) +2: we start with the number we have add two for each on the main line plus two more, one on each end.

    It can be shown that the closed form is 2n^2 - 2n+1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2007
    Posts
    9
    Okay so the “main line” is the bit through the center



    I don’t quite understand what you mean by

    “We a to add 2 rectangles, one above and one below, each of the rectangles on the main line plus one on each end.”

    Are you referring to these bits

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    Using the formula  S_{n+1} = S_n + 2(2n-1) + 2 , look at picture 3:


    Starting from picture 2, we add 2 rectangles above each square along the main line (including the middle one which already has two squares attached to it). Then we add 2 rectangles to the end to get the third picture.
    Attached Thumbnails Attached Thumbnails Mathematical Induction-untitled.jpg  
    Last edited by tukeywilliams; August 2nd 2007 at 11:54 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Aug 2007
    Posts
    9
    Thanks Plato and tukeywilliams I think I got it does this sound right

    Proving Via Mathematical Induction

    2k - 2k + 1


    Explain how that Works Sn+1 = Sn + 2(2n – 1) +2

    Then prove that 2k - 2k + 1 Works when n = 1

    2 x 1 - 2 x 1 + 1 = 1

    Then Prove that it works when n = k + 1

    2(k+1) - 2(k+1) + 1 = 2k - 2k + 1 + 4k
    2(k + 2k + 2) –2k + 2 +1 = 2k + 2k +1
    2k + 4k + 4 –2k + 3 = 2k + 2k +1
    2k + 2k + 1 =2k + 2k +1
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    yes that is correct.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    Quote Originally Posted by Quill View Post
    Thanks Plato and tukeywilliams I think I got it does this sound right

    Proving Via Mathematical Induction

    2k - 2k + 1

    Explain how that Works Sn+1 = Sn + 2(2n – 1) +2

    Then prove that 2k - 2k + 1 Works when n = 1

    2 x 1 - 2 x 1 + 1 = 1

    Then Prove that it works when n = k + 1

    2(k+1) - 2(k+1) + 1 = 2k - 2k + 1 + 4k
    2(k + 2k + 2) –2k + 2 +1 = 2k + 2k +1
    2k + 4k + 4 –2k + 3 = 2k + 2k +1
    2k + 2k + 1 =2k + 2k +1
    Proof: We use induction on  n . Base case: For  n = 1 ,  2(1)^2 -2(1)+1 = 1 . Inductive step: Suppose now as inductive hypothesis that  2k^2 -2k+1 is true for some positive integer  k . Then  2(k+1)^2 - 2(k+1) + 1 =  2k^2 + 4k + 2 - 2k - 2 + 1 = 2k^2 +2k + 1 as required. Conclusion: Hence, by induction,  2n^2 +2n + 1 is true for all positive integers  n .  \square

    Your second line followed incorrectly from your first line (i.e.  2(k^2 + 2k +2) - 2k +2 +1 = 2k^2 + 2k +1 ).
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Aug 2007
    Posts
    9
    Cool thank you very much

    *Edit* Just wondering how would I reference this sight in a assignment and would it be considered plagiarism because u showed me how to do the question.
    Last edited by Quill; August 3rd 2007 at 01:48 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 31st 2010, 03:31 PM
  2. Mathematical induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 30th 2010, 05:54 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. mathematical induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 13th 2009, 05:29 PM
  5. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 18th 2009, 08:35 AM

Search Tags


/mathhelpforum @mathhelpforum