文档介绍：Discrete Mathematics
AN INTRODUCTION TO PROOFS BINATORICS
KEVIN FERLAND
Bloomsburg University
HOUGHTON PANY
Boston New York
To Sarah and Ethan
Publisher: Richard Stratton
Senior Sponsoring Editor: Molly Taylor
Senior Marketing Manager: Jennifer Jones
Senior Development Editor: Maria Morelli
Senior Project Editor: Tamela Ambush
Art and Design Manager: Jill Haber
Cover Design Manager: Anne S. Katzeff
position Buyer: Chuck Dutton
New Title Project Manager: Susan Peltier
Editorial Associate: Andrew Lipsett
Editorial Assistant: Joanna Carter-O’Connell
Cover image: © Peter Samuels
Copyright © 2009 by Houghton pany. All rights
reserved.
No part of this work may be reproduced or transmitted in
any form or by any means, electronic or mechanical,
including photocopying and recording, or by any
information storage or retrieval system without the prior
written permission of Houghton pany unless
such copying is expressly permitted by federal copyright
law. Address inquiries to College Permissions, Houghton
pany, 222 Berkeley Street, Boston,
MA 02116-3764.
Printed in the .
Library of Congress Control Number: 2007941451
ISBN-10: 0-618-41538-6
ISBN-13: 978-0-618-41538-0
123456789-CRW-12 11 10 09 08
Contents
Preface v
Acknowledgments viii
0 Representing Numbers 1
Part I Proofs 7
1 Logic and Sets 9 Irrational Numbers 142
Statement Forms and Logical Modular Arithmetic 150
Equivalences 9 Chapter 3 Review Problems 162
Set Notation 23
Quantifiers 32 4 Indexed by Integers 167
Set Operations and Identities 42 Sequences, Indexing, and Recursion 167
Valid Arguments 54 Sigma Notation 177
Chapter 1 Review Problems 65 Mathematical Induction,
an Introduction 185
2 Basic Proof Writing 69 Induction and Summations 195
Direct Demonstration 69 Strong Induction 201
General Demonstration (Part 1) 75 The Binomial Theorem 211
General Demonstration (Part 2) 82 Chapter 4 Revi