Course 4 Unit 8 - Counting Methods and Induction ©2010

This unit continues and formalizes the previous informal work that students have done with systematic counting in earlier courses (although review of earlier work is built into the investigations for those students that may have missed some of the earlier work). As is often the case in Core-Plus Mathematics, the emphasis is on problem solving, reasoning, and sense making. In particular, students are encouraged to count by carefully analyzing, representing, and enumerating in a given situation. Formulas are developed and used, but it is important for students to base their formula work on understanding. Proof by mathematical inductions is also developed in a precise, yet sense-making way. (See the CPMP Courses 1-4 descriptions.)

Unit Overview
This unit provides an introduction to combinatorics, the mathematics of systematic counting. Students learn fundamental concepts and methods used to solve combinatorial problems. The major counting concepts and techniques developed are the Multiplication Principle of Counting, combinations, and permutations. Additional important topics include the Addition Principle of Counting, systematic lists, counting trees, and a systematic analysis of order and repetition when counting the number of possible choices from a collection. Related topics include the Binomial Theorem, Pascal's triangle, and the General Multiplication Rule for Probability. Two new methods of mathematical reasoning and proof are developed, combinatorial reasoning and mathematical induction.

 Objectives of the Unit Develop the skill of careful counting in a variety of contexts Understand and apply a variety of counting techniques, including the Multiplication Principle of Counting, the Addition Principle of Counting, counting trees, and systematic lists Understand and apply the issues of order and repetition when counting the number of possible choices from a collection Solve counting problems involving combinations and permutations Understand and apply the Binomial Theorem Understand and apply connections among combinations, the Binomial Theorem, and Pascal's triangle Apply counting methods to probability situations in which all outcomes are equally likely Extend understanding of and apply the General Multiplication Rule for Probability Develop the skill of combinatorial reasoning, including use in proofs Understand and carry out proofs by mathematical induction Understand and carry out proofs using indirect reasoning and the Least Number Principle

Sample Overview
Unit 8 Lesson 3 develops the Principle of Mathematical Induction. In this lesson, students learn how to do proofs by mathematical induction in a precise, yet sense-making way. They also consider the Least Number Principle, how it is used in indirect proofs, and how this proof method compares to proofs by mathematical induction.
The sample below is Investigation 1, "Infinity, Recursion, and Mathematical Induction." In this investigation, students will carry out and develop an understanding of induction proofs. Sometimes, before the proof begins, students need to decide what to prove. This is often done by experimenting and looking for a pattern. There are typically two relevant patterns—a recursive pattern (sometimes expressed as a recursive formula) and a closed-form pattern (sometimes expressed as a function rule). It is the closed-form pattern that is proven with mathematical induction. The recursive pattern is essential for the induction step in the induction proof. It is important to note that the recursive pattern must also be proven, often by reasoning about the context, and it must be done before using the recursive relationship in the induction proof.

Instructional Design
Throughout the curriculum, interesting problem contexts serve as the foundation for instruction. As lessons unfold around these problem situations, classroom instruction tends to follow a four-phase cycle of classroom activities—Launch, Explore, Share and Summarize, and Apply. This instructional model is elaborated under Instructional Design.