Acknowledgments This New Edition I have many people to thank for their help in the preparation of this second edition. My colleagues at Harvey Mudd College,Professor Arthur Benjamin and An- drew Bernoff,have used preliminary drafts of this second edition in their class- rooms and have provided valuable feedback.A number of their students sent me comments and suggestions;many thanks to Jon Azose,Alan Davidson,Rachel Harris,Christopher Kain,John McCullough,and Hadley Watson. For a number of years,my colleagues at Johns Hopkins University have been teaching our discrete mathematics course using this text.I especially want to thank Donniell Fishkind and Fred Torcaso for their helpful comments and encourage- ment. It has been a pleasure working with Bob Pirtle,my editor at Brooks/Cole.I greatly value his support,encouragement,patience,and flexibility. Brooks/Cole arranged for independent reviewers to provide feedback on this revision.Their comments were valuable and helped improve this new edition. Many thanks to Mike Daven (Mount Saint Mary College),Przemo Kranz(Univer- sity of Mississippi),Jeff Johannes(The State University of New York Geneseo), and Michael Sullivan(San Diego State University). The beautiful cover photograph is by my friend and former neighbor(and bridge partner)Albert Kocourek.This glorious image,entitled New Wharf,was taken in Maryland on the eastern shore of the Chesapeake Bay.Thank you,Al! More of Al's artwork can be seen on his website,www.albertkocourek.com Thanks also to Jeanne Calabrese for the beautiful design of the cover. The first edition had a number of errors.I greatly appreciate feedback from var- ious students and instructors for bringing these mistakes to my attention.In particu- lar,I thank Seema Aggarwal,Ben Babcock,Richard Belshoff,Kent Donnelly,Usit Duongsaa,Donniell Fishkind,George Huang,Sandi Klavzar,Peter Landweber, George Mackiw,Ryan Mansfield,Gary Morris,Evan O'Dea,Levi Ortiz,Russ Rut- ledge,Rachel Scheinerman,Karen Seyffarth,Douglas Shier,and Kimberly Tucker. From the First Edition These acknowledgments appeared in the first edition of this book;I still owe the individuals mentioned below a debt of gratitude. During academic year 1998-99,students at Harvey Mudd College.Loyola College in Maryland,and the Johns Hopkins University used a preliminary version of this text.I am grateful to George Mackiw (Loyola)and Greg Levin(Harvey Mudd)for test-piloting this text.They provided me with many helpful comments. corrections,and suggestions. XXV
Acknowledgments This New Edition I have many people to thank for their help in the preparation of this second edition. My colleagues at Harvey Mudd College, Professor Arthur Benjamin and Andrew Bemoff, have used preliminary drafts of this second edition in their classrooms and have provided valuable feedback. A number of their students sent me comments and suggestions; many thanks to Jon Azose, Alan Davidson, Rachel Harris, Christopher Kain, John McCullough, and Hadley Watson. For a number of years, my colleagues at Johns Hopkins University have been teaching our discrete mathematics course using this text. I especially want to thank Donniell Fishkind and Fred Torcaso for their helpful comments and encouragement. It has been a pleasure working with Bob Pirtle, my editor at Brooks/Cole. I greatly value his support, encouragement, patience, and flexibility. Brooks/Cole arranged for independent reviewers to provide feedback on this revision. Their comments were valuable and helped improve this new edition. Many thanks to Mike Daven (Mount Saint Mary College), Przemo Kranz (University of Mississippi), Jeff Johannes (The State University of New York Geneseo), and Michael Sullivan (San Diego State University). The beautiful cover photograph is by my friend and former neighbor (and bridge partner) Albert Kocourek. This glorious image, entitled New Wharf, was taken in Maryland on the eastern shore of the Chesapeake Bay. Thank you, AI! More of Al's artwork can be seen on his website, www. albertkocourek. com. Thanks also to Jeanne Calabrese for the beautiful design of the cover. The first edition had a number of errors. I greatly appreciate feedback from various students and instructors for bringing these mistakes to my attention. In particular, I thank Seema Aggarwal, Ben Babcock, Richard Belshoff, Kent Donnelly, U sit Duongsaa, Donniell Fishkind, George Huang, Sandi Klavzar, Peter Landweber, George Mackiw, Ryan Mansfield, Gary Morris, Evan O'Dea, Levi Ortiz, Russ Rutledge, Rachel Scheinerman, Karen Seyffarth, Douglas Shier, and Kimberly Tucker. From the First Edition These acknowledgments appeared in the first edition of this book; I still owe the individuals mentioned below a debt of gratitude. During academic year 1998-99, students at Harvey Mudd College, Loyola College in Maryland, and the Johns Hopkins University used a preliminary version of this text. I am grateful to George Mackiw (Loyola) and Greg Levin (Harvey Mudd) for test-piloting this text. They provided me with many helpful comments, corrections, and suggestions. XXV
XXVI Acknowledgments I would especially like to thank the many students at these various institutions who had to endure typo-ridden first drafts.They offered many valuable suggestions that improved the text.In particular,I received helpful comments from all of the following: Harvey Mudd:Jesse Abrams,Rob Adams,Gillian Allen,Matt Brubeck,Zeke Burgess,Nate Chessin,Jocelyn Chew,Brandon Duncan,Adam Fischer,Brad Forrest,Jon Erickson,Cecilia Giddings,Joshdan Griffin,David Herman,Doug Honma,Eric Huang,Keith Ito,Masashi Ito,Leslie Joe,Mike Lauzon,Colin Little, Dale Lovell,Steven Matthews,Laura Mecurio,Elizabeth Millan,Joel Miller,Greg Mulert,Bryce Nichols,Lizz Norton,Jordan Parker,Niccole Parker,Jane Pratt, Katie Ray,Star Roth,Mike Schubmehl,Roy Shea,Josh Smallman,Virginia Stoll, Alex Teoh,Jay Trautman,Richard Trinh,Kim Wallmark,Zach Walters,Titus Winters,Kevin Wong,Matthew Wong,Nigel Wright,Andrew Yamashita,Steve Yan,and Jason Yelinek. Loyola:Richard Barley and Deborah Kunder. Johns Hopkins:Adam Cannon,William Chang,Lara Diamond,Elias Fenton, Eric Hecht,Jacqueline Huang,Brian lacoviello,Mark Schwager,David Tucker, Aaron Whittier,and Hani Yasmin. Art Benjamin(Harvey Mudd College)contributed a collection of problems he uses when he teaches discrete mathematics;many of these problems appear in this text.Many years ago,Art was my teaching assistant when I first taught discrete mathematics.His help in developing that course undoubtedly has an echo in this book. Thanks to Ran Libeskind-Hadas(also from Harvey Mudd)for contributing his collection of problems. I had many enjoyable philosophical discussions with Mike Bridgland(Center for Computer Sciences)and Paul Tanenbaum(Army Research Laboratory).They kept me logically honest and gave excellent advice on how to structure my ap- proach.Paul carefully read through an early draft of the book and made many helpful suggestions. Thanks to Laura Tateosian,who drew the cartoon for the hint to Exercise 47.7. Brooks/Cole arranged for an early version of this book to be reviewed by vari- ous mathematicians.I thank the following individuals for their helpful suggestions and comments:Douglas Burke(University of Nevada-Las Vegas),Joseph Gallian (University of Minnesota),John Gimbel(University of Alaska-Fairbanks),Henry Gould (West Virginia University),Arthur Hobbs (Texas A&M University),and George MacKiw (Loyola College in Maryland). Lara Diamond painstakingly read through every sentence,uncovering numer- ous mathematical errors;I appreciate this tremendous support.Thank you,Lara. I would like to believe that with so many people looking over my shoulder,all the errors have been found,but this is ridiculous.I am sure I have made many more errors than these people could find.This leaves some more for you,my reader,to find.Please tell me about them.(Send email to ersojhu.edu.) I am lucky to work with wonderful colleagues and graduate students in the Department of Applied Mathematics and Statistics at Johns Hopkins.In one way or another,they all have influenced me and my teaching and in this way contributed to this book.I thank them all and would like to add particular mention to these
xxvi Acknowledgments I would especially like to thank the many students at these various institutions who had to endure typo-ridden first drafts. They offered many vaiuable suggestions that improved the text. In particular, I received helpful comments from all of the following: Harvey Mudd: Jesse Abrams, Rob Adams, Gillian Allen, Matt Brubeck, Zeke Burgess, Nate Chessin, Jocelyn Chew, Brandon Duncan, Adam Fischer, Brad Forrest, Jon Erickson, Cecilia Giddings, Joshdan Griffin, David Herman, Doug Honma, Eric Huang, Keith Ito, Masashi Ito, Leslie Joe, Mike Lauzon, Colin Little, Dale Lovell, Steven Matthews, Laura Mecurio, Elizabeth Millan, Joel Miller, Greg Mulert, Bryce Nichols, Lizz Norton, Jordan Parker, Niccole Parker, Jane Pratt, Katie Ray, Star Roth, Mike Schubmehl, Roy Shea, Josh Smallman, Virginia Stoll, Alex Teoh, Jay Trautman, Richard Trinh, Kim Wallmark, Zach Walters, Titus Winters, Kevin Wong, Matthew Wong, Nigel Wright, Andrew Yamashita, Steve Yan, and Jason Yelinek. Loyola: Richard Barley and Deborah Kunder. Johns Hopkins: Adam Cannon, William Chang, Lara Diamond, Elias Fenton, Eric Hecht, Jacqueline Huang, Brian Iacoviello, Mark Schwager, David Tucker, Aaron Whittier, and Hani Yasmin. Art Benjamin (Harvey Mudd College) contributed a collection of problems he uses when he teaches discrete mathematics; many of these problems appear in this text. Many years ago, Art was my teaching assistant when I first taught discrete mathematics. His help in developing that course undoubtedly has an echo in this book. Thanks to Ran Libeskind-Hadas (also from Harvey Mudd) for contributing his collection of problems. I had many enjoyable philosophical discussions with Mike Bridgland (Center for Computer Sciences) and Paul Tanenbaum (Army Research Laboratory). They kept me logically honest and gave excellent advice on how to structure my approach. Paul carefully read through an early draft of the book and made many helpful suggestions. Thanks to Laura Tateosian, who drew the cartoon for the hint to Exercise 4 7. 7. Brooks/Cole arranged for an early version of this book to be reviewed by various mathematicians. I thank the following individuals for their helpful suggestions and comments: Douglas Burke (University of Nevada-Las Vegas), Joseph Gallian (University of Minnesota), John Gimbel (University of Alaska-Fairbanks), Henry Gould (West Virginia University), Arthur Hobbs (Texas A&M University), and George MacKiw (Loyola College in Maryland). Lara Diamond painstakingly read through every sentence, uncovering numerous mathematical errors; I appreciate this tremendous support. Thank you, Lara. I would like to believe that with so many people looking over my shoulder, all the errors have been found, but this is ridiculous. I am sure I have made many more errors than these people could find. This leaves some more for you, my reader, to find. Please tell me about them. (Send email to ers@jhu. edu.) I am lucky to work with wonderful colleagues and graduate students in the Department of Applied Mathematics and Statistics at Johns Hopkins. In one way or another, they all have influenced me and my teaching and in this way contributed to this book. I thank them all and would like to add particular mention to these
Acknowledgments xxvii Bob Serfling was department chair when I first came to Hopkins;he empowered and trusted me to develop the discrete mathematics curriculum for the department. Over more than a decade,I have received tremendous support,encouragement, and advice from my current department chair,John Wierman.And Lenore Cowen not only contributed her enthusiasm,but also read over various portions of the text and made helpful suggestions. Thanks also to Gary Ostedt,Carole Benedict,and their colleagues at Brooks/ Cole.It was a pleasure working with them.Gary's enthusiasm for this project often exceeded my own.Carole was my main point of contact with Brooks/Cole and was always helpful,reliable,and cheerful. Finally,thanks (and hugs and kisses)to my wife,Amy,and to our children, Rachel,Danny,Naomi,and Jonah,for their patience,support,and love throughout the writing of this book. Edward R.Scheinerman
Acknowledgments xxvii Bob Serfling was department chair when I first came to Hopkins; he empowered and trusted me to develop the discrete mathematics curriculum for the department. Over more than a decade, I have received tremendous support, encouragement, and advice from my current department chair, John Wierman. And Lenore Cowen not only contributed her enthusiasm, but also read over various portions of the text and made helpful suggestions. Thanks also to Gary Ostedt, Carole Benedict, and their colleagues at Brooks/ Cole. It was a pleasure working with them. Gary's enthusiasm for this project often exceeded my own. Carole was my main point of contact with Brooks/Cole and was always helpful, reliable, and cheerful. Finally, thanks (and hugs and kisses) to my wife, Amy, and to our children, Rachel, Danny, Naomi, and Jonah, for their patience, support, and love throughout the writing of this book. Edward R. Scheinerman
CHAPTER Fundamentals The cornerstones of mathematics are definition,theorem,and proof.Definitions specify precisely the concepts in which we are interested,theorems assert exactly what is true about these concepts,and proofs irrefutably demonstrate the truth of these assertions. Before we get started,though,we ask a question:Why? 1 Joy Why? Before we roll up our sleeves and get to work in earnest,I want to share with you Please also read the To the Student preface,where we a few thoughts on the question:Why study mathematics? briefly address the Mathematics is incredibly useful.Mathematics is central to every facet of questions:What is modern technology:the discovery of new drugs,the scheduling of airlines,the mathematics,and what is reliability of communication,the encoding of music and movies on CDs and discrete mathematics?We DVDs,the efficiency of automobile engines,and on and on.Its reach extends also give important advice on how to read a far beyond the technical sciences.Mathematics is also central to all the social mathematics book. sciences,from understanding the fluctuations of the economy to the modeling of social networks in schools or businesses.Every branch of the fine arts-including literature,music,sculpture,painting,and theater-has also benefited from(or been inspired by)mathematics. Because mathematics is both flexible(new mathematics is invented daily)and rigorous (we can incontrovertibly prove our assertions are correct),it is the finest analytic tool humans have developed. The unparalleled success of mathematics as a tool for solving problems in science,engineering,society,and the arts is reason enough to engage actively this wonderful subject.We mathematicians are immensely proud of the accomplish- ments that are fueled by mathematical analysis.However,for many of us,this is not the primary motivation in studying mathematics. 1
CHAPTER 1 Fundamentals The cornerstones of mathematics are definition, theorem, and proof. Definitions specify precisely the concepts in which we are interested, theorems assert exactly what is true about these concepts, and proofs irrefutably demonstrate the truth of these assertions. Before we get started, though, we ask a question: Why? 1 Joy Please also read the To the Student preface, where we briefly address the questions: What is mathematics, and what is discrete mathematics? We also give important advice on how to read a mathematics book. Why? Before we roll up our sleeves and get to work in earnest, I want to share with you a few thoughts on the question: Why study mathematics? Mathematics is incredibly useful. Mathematics is central to every facet of modem technology: the discovery of new drugs, the scheduling of airlines, the reliability of communication; the encoding of music and movies on CDs and DVDs, the efficiency of automobile engines, and on and on. Its reach extends far beyond the technical sciences. Mathematics is also central to all the social sciences, from understanding the fluctuations of the economy to the modeling of social networks in schools or businesses. Every branch of the fine arts-including literature, music, sculpture, painting, and theater-has also benefited from (or been inspired by) mathematics. Because mathematics is both flexible (new mathematics is invented daily) and rigorous (we can incontrovertibly prove our assertions are correct), it is the finest analytic tool humans have developed. The unparalleled success of mathematics as a tool for solving problems in science, engineering, society, and the arts is reason enough to engage actively this wonderful subject. We mathematicians are immensely proud of the accomplishments that are fueled by mathematical analysis. However, for many of us, this is not the primary motivation in studying mathematics
Chapter 1 Fundamentals The Agony and the Ecstasy Why do mathematicians devote their lives to the study of mathematics?For most of us,it is because of the joy we experience when doing mathematics. Mathematics is difficult for everyone.No matter what level of accomplishment or skill in this subject you (or your instructor)have attained,there is always a harder,more frustrating problem waiting around the bend.Demoralizing?Hardly! The greater the challenge,the greater the sense of accomplishment we experience when the challenge has been met.The best part of mathematics is the joy we experience in practicing this art. Most art forms can be enjoyed by spectators.I can delight in a concert per- formed by talented musicians,be awestruck by a beautiful painting,or be deeply moved by literature.Mathematics,however,releases its emotional surge only for those who actually do the work. I want you to feel the joy,too.So at the end of this brief section there is a single problem for you to tackle.In order for you to experience the joy,do not under Conversely,if you have solved this problem.do not any circumstances let anyone help you solve this problem.I hope that when offer your assistance to you first look at the problem,you do not immediately see the solution but,rather, others:you don't want to have to struggle with it for a while.Don't feel bad:I've shown this problem to spoil their fun. extremely talented mathematicians who did not see the solution right away.Keep working and thinking-the solution will come.My hope is that when you solve this puzzle,it will bring a smile to your face.Here's the puzzle: 1 Exercise 1.1.Simplify the following algebraic expression: (x-a)(x-b)(x-c).··(x-z). 2 Definition Mathematics exists only in people's minds.There is no such"thing"as the num- ber 6.You can draw the symbol for the number 6 on a piece of paper,but you can't physically hold a 6 in your hands.Numbers,like all other mathematical objects, are purely conceptual. Mathematical objects come into existence by definitions.For example,a num- ber is called prime or even provided it satisfies precise,unambiguous conditions. These highly specific conditions are the definition for the concept.In this way, we are acting like legislators,laying down specific criteria such as eligibility for a government program.The difference is that laws may allow for some ambiguity, whereas a mathematical definition must be absolutely clear. Let's take a look at an example. Definition 2.1 (Even)An integer is called even provided it is divisible by two. In a definition,the word(s) being detined are set in Clear?Not entirely.The problem is that this definition contains terms that we italic type. have not yet defined,in particular integer and divisible.If we wish to be terribly
2 Chapter 1 Fundamentals Conversely, if you have solved this problem, do not offer your assistance to others; you don't want to spoil their fun. Exercise The Agony and the Ecstasy v Why do mathematicians devote their lives to the study of mathematics? For most of us, it is because of the joy we experience when doing mathematics. Mathematics is difficult for everyone. No matter what level of accomplishment or skill in this subject you (or your instructor) have attained, there is always a harder, more frustrating problem waiting around the bend. Demoralizing? Hardly! The greater the challenge, the greater the sense of accomplishment we experience when the challenge has been met. The best part of mathematics is the joy we experience in practicing this art. Most art forms can be enjoyed by spectators. I can delight in a concert performed by talented musicians, be awestruck by a beautiful painting, or be deeply moved by literature. Mathematics, however, releases its emotional surge only for those who actually do the work. I want you to feel the joy, too. So at the end ofthis brief section there is a single problem for you to tackle. In order for you to experience the joy, do not under any circumstances let anyone help you solve this problem. I hope that when you first look at the problem, you do not immediately see the solution but, rather, have to struggle with it for a while. Don't feel bad: I've shown this problem to extremely talented mathematicians who did not see the solution right away. Keep working and thinking-the solution will come. My hope is that when you solve this puzzle, it will bring a smile to your face. Here's the puzzle: 1.1. Simplify the following algebraic expression: (x - a)(x - b)(x -c)··· (x - z). 2 Definition Mathematics exists only in people's minds. There is no such "thing" as the number 6. You can draw the symbol for the number 6 on a piece of paper, but you can't physically hold a 6 in your hands. Numbers, like all other mathematical objects, are purely conceptual. Mathematical objects come into existence by definitions. For example, anumber is called prime or even provided it satisfies precise, unambiguous conditions. These highly specific conditions are the definition for the concept. In this way, we are acting like legislators, laying down specific criteria such as eligibility for a government program. The difference is that laws may allow for some ambiguity, whereas a mathematical definition must be absolutely clear. Let's take a look at an example. Definition 2.1 (Even) An integer is called even provided it is divisible by two. In a definition. the word(s) being defined are set in italic type. Clear? Not entirely. The problem is that this definition contains terms that we have not yet defined, in particular integer and divisible. If we wish to be terribly