Course Profile Geometry and Discrete Mathematics (MGA4U), Grade 12, University Preparation, Catholic

Unit 5: Mathematical Induction and Combinatorics

Time: 19 hours

Unit Description

Students use pattern recognition to derive formulas for the terms and sums of arithmetic and geometric sequences and series. Sigma notation is used to express a series as a sum of related terms. Mathematical induction is introduced as an effective means of proving sequence- and series-related results. Inductive reasoning skills are extended in the proof of other algebraic results. Using factorial notation, permutations, and combinations, students solve introductory counting problems.

Activity 5.1: ReCurses! Foiled Again!

Time: 3.5 hours

Description

Students use recursive thinking techniques and deductive reasoning skills to develop the conceptual foundation upon which mathematical induction will be introduced.

Strand(s) & Learning Expectations

Ontario Catholic School Graduate Expectations

CGE2b - an effective communicator who reads, understands, and uses written materials effectively;

CGE3c - a reflective and critical thinker who thinks reflectively and creatively to evaluate situations and solve problems;

CGE4b - a self-directed, responsible, life long learner who demonstrates flexibility and adaptability;

CGE4f - a self-directed, responsible, life long learner who applies effective communication, decision-making, problem-solving, time and resource management skills.

Strand(s): Discrete Mathematics, Proof and Problem Solving

Overall Expectations

DMV.02 - prove results, using mathematical induction;

PSV.02 - solve problems, using a variety of strategies;

PSV.03 - complete significant problem-solving tasks independently.

Specific Expectations

DM2.01 - demonstrate an understanding of the principle of mathematical induction;

DM2.02 - use sigma notation to represent a series or the sum of a series;

PS2.02 - generate multiple solutions to the same problem;

PS3.01 - solve problems of significance, working independently, as individuals and in small groups;

PS3.03 - demonstrate significant learning and the effective use of skills in tasks such as solving challenging problems, researching problems, applying mathematics, creating proofs, using technology effectively, and presenting course topics or extensions of course topics.

Planning Notes

· These activities have been developed with the intention that they would be conducted sequentially. However, little or no modification would be required should the teacher wish to have the students perform only one of the activities.

Activity 5.1A: But Series-ly, Folks

Time: 1 hour

Description

After first exploring summation notation, students determine the sum of a series using pattern recognition and deductive reasoning. Using an introduction to infinite series as the context, this activity prepares students for the use of the recursive thinking skills required for the next activity and ultimately, proof by mathematical induction.

Prior Knowledge & Skills

· Students should possess a working knowledge of arithmetic and geometric sequences and series, including formulas to generate nth terms and sums.

· Although prior knowledge of sequences and series is not essential for this activity, it does provide some familiarity to the content. Since sequences and series (as well as sigma notation) do figure prominently in later activities, so it is recommended that the teacher introduce or help students consolidate requisite knowledge and skills.

Planning Notes

· Although intended as a self-discovery exercise, the time allotted for this activity could be shortened if conducted as a teacher-facilitated class problem.

Teaching/Learning Strategies

A. Teacher Facilitation

· Students may work alone, or in pairs, for this activity.

· The Catholic School Graduate Expectations are addressed as indicated throughout this activity.

B. Student Activity

Suggestions for teacher facilitation are included throughout this activity in italics. Some solutions are included to aid in the flow of the activity.

1. Write the first five terms of the sequence defined by .

2. Find the sum of these terms.

3. Writing out the terms of a series can sometimes get a bit awkward, especially if the number of terms is large. Note, however, that each of the terms of our series has the same “form,” given by . All that is needed to generate the 7th term (for example) is to replace n with 7 and evaluate. Mathematicians use summation or sigma notation to represent sums of sequences. The notation can be used to represent the sum of the first five terms of our sequence. Each term in the series has the form , as indicated by the expression to the right of the sigma (S). The terms themselves are determined by substituting the natural numbers between 1 and 5 for n, as indicated by the lower and upper indices. [CGE2b]

4. Find, the sum of the first k terms, for k = 1, 2, 3, 4, and 5, using the following chart:
(The first row has been provided.)

Summation	Series Expansion	Sum

		…
…	…	…

5. Describe any patterns that may emerge. The two most common patterns will probably be (a) the difference between the numerator and denominator is always 1, and (b) adding the numerator and denominator of the previous sum will generate the numerator of the current sum (a recursive definition). [CGE3c]

6. How could the sum of the first seven terms of this series be determined without expanding?

7. Let S₃ represent the sum of the first three terms (so S₈ would be the sum of the first eight terms, S₂₁ would be the sum of the first twenty-one terms, etc.). Determine S₁₁ without expanding.

8. Determine S_n, a general formula for the sum of the first n terms. (Be sure to simplify as much as possible.) Verify this conjecture using the appropriate sum of a series formula. As this is a geometric series, students can verify their conjecture using the formula , where .

9. Using your formula, determine S₁₅, S₁₇, and S₂₀.

10. What conclusions can be inferred about the sum S_n as n gets larger? The numerator will always be one less than the denominator, but this difference will become less and less significant, as the value of the fraction will get closer and closer to 1.

11. Determine (i.e., as the value of n gets infinitely large, what will happen to the sum?) Although students have not been exposed to limits, they may have some intuitive sense of limits at infinity, especially by using the bracketed phrasing of the question. [CGE4b]

12. How could the following diagram be used to illustrate the findings of this activity?

The areas of the sections in the diagram can be used to represent the terms of the series in this activity. The terms become smaller and smaller. In fact, as nàµ, the individual terms become infinitely small, and for this reason, this infinite series can be shown to have a finite sum of 1. Using this diagram, students may have a better understanding of the sum of this infinite series.

C. Follow-Up Skills

Time: 0.75 hours

1. The teacher should supplement the preceding activity with problems reviewing arithmetic and geometric sequences and series.

2. Students may repeat the activity with another series, such as . [CGE4b]

3. The following diagram shows how to construct a Sierpinski Triangle.

If the pattern is continued indefinitely, what fraction of the area of the original triangle will be shaded? [CGE4f]

D. Supplemental Research

1. Define a collapsing or telescoping series. A series such as , which expands to , is considered to be collapsing because the middle terms, when grouped differently, all cancel out.

2. What are Zeno’s Paradoxes? How they be related to the findings of this activity? Zeno’s Paradoxes involve problems dealing with the sums of infinite series. One of these paradoxes could in fact be modelled by Activity 5.1A.

3. Who is Leonardo da Pisa? Research his contributions to the study of sequences and series. Leonardo da Pisa is otherwise known as Fibonacci. His solution to a problem regarding a population of rabbits gave rise to the Fibonacci sequence, which occurs frequently in the biological and physical sciences.

Assessment & Evaluation of Student Achievement

The Catholic School Graduate Expectations can be assessed using an appropriate observational checklist or by student self-diagnostic assessment. It is recommended that the students complete at least the Student Activity section individually. Question 10 of the activity can be used to assess Communication skills, especially the use of appropriate mathematical vocabulary and the degree of clarity in establishing and describing a connection with the activity. Should the teacher wish to repeat the activity with a different series (as suggested in Question 2 of the Follow-Up Skills section), assessment should focus on Knowledge/Understanding, specifically the ability to use an algorithm to solve a problem. Question 3 of the Follow-Up Skills section addresses Thinking/Inquiry/Problem Solving skills, e.g., the creation of an algebraic model; making inferences, conclusions, and justifications, etc. If used as a journal topic, Communication skills can also be stressed in this question.

Activity 5.1B: Pick A Tooth, Any Tooth

Time: 1.25 hours

Description

Given a geometric problem, the number of toothpicks required to construct a triangular figure, students collect, plot, and analyse data. They then attempt to fit an algebraic model to this data using first and second difference and/or graphing techniques. In analysing the data, students use recursive thinking by basing their data collection for a given triangle on that of the previous triangle. The generalizations that emerge from this activity provide a framework for proof by mathematical induction, revisited in greater detail in Activity 5.2 – Induction-Duction, What’s Your Function?

Prior Knowledge & Skills

· Students will require curve-fitting techniques, and thus the ability to determine simple polynomial equations from their respective graphs.

· First and second differences will be used to generate quadratic equations.

Planning Notes

· Ideally, students should be provided with toothpicks to perform this activity. While they are not essential for its completion, having manipulatives should increase the appeal of the activity, and in addition add tactile context to the meaning of “constructing triangles.”

· Graph paper should be made available to all students.

Teaching/Learning Strategies

A. Teacher Facilitation

· Students may work alone or in pairs for this activity.

· This activity refers to first and second differences frequently. Teachers may use the term finite differences interchangeably with first and second differences.

· The Catholic School Graduate Expectations are addressed as indicated throughout this activity.

B. Student Activity

Suggestions for teacher facilitation are included throughout this activity in italics. Some solutions are included to aid in the flow of the activity.

1. The diagram above demonstrates the construction of triangles of side lengths one and two respectively. How many toothpicks does a triangle of side length one require?

2. How many toothpicks does a triangle of side length two require?

3. Call the triangle of side length one D₁, and the triangle of length two Î₂. Construct D₃ and count the toothpicks. How many are there?

4. Although it may seem trivial, it is theoretically feasible to speak of a triangle of side length 0. How many toothpicks are required for Î₀?

5. Complete this table:

Triangle Side Length	Total Number of Toothpicks
0
1
2
3

6. The number of toothpicks required to construct Î_k can be determined simply by counting them. As the value of k gets larger, however, this may prove to be more difficult. How else could this be done? Students could plot the totals on a grid and curve fit, they may attempt to develop an algebraic formula, or they could use a recursive approach (determining the total number of toothpicks for one triangle given the total number from the previous triangle). This last approach that will be recommended for this activity. [CGE4b]

7. Given Î₂, construct Î₃. How many additional toothpicks are required to construct the new triangle? 9 additional toothpicks are required. Construct Î₄. How many toothpicks are required to complete the new triangle? Students may wish to tackle this problem by counting the number of toothpicks required to construct the sides, the bottom, and the “insides” of the new triangle.

8. Given a triangle with side length k, how many new toothpicks would be required to make a triangle with side length k + 1? Students should discern a pattern in the number of toothpicks required to construct a new triangle from the given triangle. In doing so, they are reasoning recursively. There are 2 toothpicks required for the ends, k + 1 toothpicks required for the bottom, and 2k toothpicks required for the “insides,” for a total of 3k + 3 or 3(k + 1) new toothpicks. [CGE3c]

9. Use this formula for the number of new toothpicks to predict the number of toothpicks needed to turn Î₄ into a Î₅. Confirm this result by constructing Î₅.

10. To be true, a general formula must apply to all possible cases. Using the formula, how many new toothpicks are required to go from Î₀ to Î₁? Does the table confirm this?

11. Mathematical models often can be extended beyond the “real world” into the abstract or theoretical. Consider the case where k = !1. How many new toothpicks does your formula predict would be necessary to go from Î_!₁ to Î₀? Extend the table to permit negative numbers. Determine the total number of toothpicks required to construct Î_!₁ and place it in the table.

12. Determine the total number of toothpicks required to construct Î_!₂ and place it in it the table.

13. Using the method of first and second differences, by graphing, or by curve fitting, predict an equation for the total number of toothpicks T given the triangle side length k. Students could also use finite differences to classify the equation as a quadratic, then use the quadratic regression function on a calculator to determine the equation. The equation is [CGE3c].

14. How many toothpicks would have to be added to Î_k to construct Î_k_{+ 1}? By adding the appropriate number of toothpicks to Î_k, what is the total number of toothpicks required to construct Î_k_{+ 1}?

15. Check the validity of this prediction using the formula for the predicted total number of toothpicks for Î_k_{+ 1}. This assures that , the formula for predicting the number of toothpicks for Î_k, will successfully predict the number of toothpicks for Î_k_{+ 1} when 3(k + 1) toothpicks are added to Î_k. Because the argument does not depend on a specific triangle, its continued success is guaranteed.

C. Follow-Up Skills

Time: 0.5 hours

· The teacher should repeatedly emphasize the recursive nature of this activity and its importance in the development of the various formulas. Given the number of toothpicks necessary to construct Î_k, one can easily calculate the number of toothpicks required to construct D_k_{+ 1}. This is the “mechanism” that drives the quest for a formula for the total number of toothpicks required for a triangle of any side length, and is the most important component of the induction process.

· The teacher should repeat this activity with squares of side length k to assess recursive thinking and problem solving skills. [CGE4b]

Assessment & Evaluation of Student Achievement

The Catholic School Graduate Expectations can be assessed using an appropriate observational rubric or by student self-diagnostic assessment. Should the teacher choose to repeat this activity with squares of side length k (as recommended in the Follow-Up Skills section), they could have the students complete it in pairs, using self-diagnostic tools in order to identify strengths and weaknesses. The teacher may wish to collect the students’ work and assess it using a rubric. Emphasis should be placed on the ability to describe relationships and draw conclusions. Organizational skills should also be considered important in this activity.

Activity 5.2: Induction-Duction, What’s Your Function?

Time: 6.25 hours

Description

In this set of activities, expressions sharing similar characteristics are examined to determine if studying patterns and making conjectures, i.e., inductive reasoning, can predict their results. Algebraic methods for solving and analysing these types of problems use deductive reasoning. In the last activity, a deductive method for proving the results of problems of this type called mathematical induction is outlined.

Strand(s) & Learning Expectations

Ontario Catholic School Graduate Expectations

CGE3c - a reflective and creative thinker who thinks reflectively and creatively to evaluate situations and solve problems;

CGE4b - a self-directed, responsible, life long learner who demonstrates flexibility and adaptability;

CGE4f - a self-directed, responsible, life long learner who applies effective communication, decision making, problem-solving, time, and resource management skills.

Strand(s): Proof and Problem Solving, Discrete Mathematics

Overall Expectations

PSV.02 - solve problems, using a variety of strategies;

PSV.03 - complete significant problem-solving tasks independently;

DMV.02 - prove results, using mathematical induction.

Specific Expectations

PS2.01 - solve problems by effectively combining a variety of problem-solving strategies;

PS2.04 - solve complex problems and present the solutions with clarity and justification;

PS3.01 - solve problems of significance, working independently, as individuals and in small groups;

DM2.01 - demonstrate an understanding of the principle of mathematical induction;

DM2.02 - use sigma notation to represent a series or the sum of a series;

DM2.03 - prove the formulas for the sums of series, using mathematical induction.

Prior Knowledge & Skills

Students should possess a working knowledge of arithmetic and geometric sequences and series, including formulas to generate nth terms and sums.

Activity 5.2A: A Guess, Even Better Than The Real Thing?

Time: 1 hour

Description

Through investigation, students develop an understanding of the difference between inductive and deductive reasoning.

Teaching/Learning Strategies

A. Teacher Facilitation

· Students should be reminded that to evaluate exactly they must show all digits and write out the answers in standard, not scientific, notation.

· Students should work on this activity independently.

· The Catholic School Graduate Expectations are addressed as indicated throughout this activity.

B. Student Activity

Suggestions for teacher facilitation are included throughout this activity in italics. Some solutions are included to aid in the flow of the activity.

1. a) By direct calculation, verify that the following pattern is true:

1 = 1 × 1 1 + 3 = 2 × 2 1 + 3 + 5 = 3 × 3 1 + 3 + 5 + 7 = 4 × 4

b) Write down the next two equations in the pattern and verify that they are true.

c) Write down the tenth equation in the pattern and verify that it is true. Is this pattern always true? Explain your answer. Some students may make the assumption that the pattern is always true, while others may note that they cannot absolutely verify if it is true. Some may refer back to the sum of an arithmetic series and show that by using the general sum , this series totals n². [CGE3c]

d) Develop a formula to express the general relationship for this pattern. There may be many forms but the most concise is given by .

2. a) Evaluate the following expressions exactly:

1 × 8 + 1 12 × 8 + 2 123 × 8 + 3 1234 × 8 + 4

b) Conjecture, then verify with a calculator, the answer to 123 456 789 × 8 + 9.

c) Will this pattern continue? Explain.

3. a) Evaluate the following expressions exactly, using any method:

b) Continue to evaluate the pattern until you get to the 7th case. Did you encounter any problems? Explain any special methods used to verify with a calculator. Not all calculators display the same number of decimal places, so this answer may vary slightly from student to student. Some students, however, may possess enough calculator skills to know how to determine decimal places that are not directly visible on their calculators. [CGE4b]

c) Predict the value of the expression . Verify this value, if possible, using a calculator. How could you verify that your prediction is absolutely correct? One possible answer is to manually calculate the product and sum, then manually perform the division.

4. Each of the problems above requires you to make an educated guess or conjecture that you may or may not be able to verify using simple algebraic methods. This type of problem solving is called inductive reasoning. Inductive reasoning uses patterns to make generalizations, but these generalizations may not always be verifiable. This means that they could be wrong.

5. a) Evaluate the following pairs of products:

i) 112 × 124, 211 × 421 ii) 312 × 221, 213 × 122 iii) 411 × 102, 114 × 201

b) For each pair of products study the numbers before and after the multiplication sign. Summarize any similarities and differences between the pairs. Students should note that not only are the digits of the factors reversed, but also the digits of their respective products.

c) Evaluate 113 × 223 and predict the answer of the product 311 × 322. Was your prediction correct? What does this illustrate about the results of inductive reasoning? Write down the pros and cons of using inductive reasoning. Students should note that recognizing patterns and making educated guesses helps to simplify elaborate calculations, but that only one example is needed to disprove a conjecture. [CGE4f]

6. The example in part (c) of the previous question is sometimes referred to as a counter-example. When a formula or relationship is stated, it is understood to be true for all cases. Thus, if even one example does not conform to this relationship, the relationship has been proven to be false.

7. a) Evaluate the sequence of powers: 11⁰, 11¹, 11², 11³.

b) Describe the pattern that seems to develop for the first few examples. The value of each power is the same when its digits are reversed. These values are called palindromic numbers. Why?

c) Determine a counter-example to disprove this pattern. The pattern fails for 11⁵.

8. Drawing conclusions from facts that are accepted as absolutely true by using logic is called deductive reasoning. While inductive reasoning is only a guess and can be refuted by even one counter-example, deductive reasoning is sound because it is based solely on simple, absolute truths (perhaps as elementary as 1 + 1 = 2).

9. Let’s reconsider Question 3c, the value of the product . Recall, we predicted its value using pattern recognition (an inductive reasoning process), but we have no way of verifying that our prediction is correct. For all we know, this particular expression could in fact be the counter-example to our pattern. Deductive reasoning enables us to verify this prediction with certainty. The product in the numerator could be calculated by hand, and while it is a daunting task, it is based on the simple principles of integer long-multiplication. Thus, multiplying by hand is a deductive process. Now consider the same product in factored form
(9)(111 111 111) ´ (9)(111 111 111) (using once again, elementary multiplicative principles). Because the denominator totals 81, the nines in the numerator reduce to 1 (an elementary division principle), leaving a product of ones, which is much easier to calculate. Using long-multiplication (a deductive process), verify that this method yields the same answer that was predicted in Question 3c. Can you feel more confident about this answer? Explain.

10. Identify historical examples in science that exemplify the idea of inductive reasoning. Focus on subjects that included some prediction of unknown data that was later verified experimentally to be true. Some possible topics may include: the periodic table, distance of planets from the sun, the model of the atom, etc.

C. Follow-Up Skills (Time: 0.25 hours)

The teacher facilitates a discussion to consolidate ideas regarding the similarities, differences, advantages, and disadvantages of using inductive and deductive reasoning prior to continuing with the next activity.

Assessment & Evaluation of Student Achievement

The Catholic School Graduate Expectations can be assessed using an appropriate observational checklist or by student self-diagnostic assessment. The teacher can use a rubric to assess the students’ understanding of mathematical content. Recognizing and describing patterns are important Thinking/Inquiry/Problem Solving and Communication skills.

Activity 5.2B: Elementary, My Dear Watson

Time: 1 hour

Description

Students apply inductive and deductive reasoning skills and their knowledge of sequences and series to algebraically (deductively) prove various problems.

Prior Knowledge & Skills

· Students should be familiar with the method of finite differences.

Teaching/Learning Strategies

A. Teacher Facilitation

· Students should work in groups of two or three for this activity.

· The teacher should supplement this activity with problems that require algebraic proofs of relationships.

· The Catholic School Graduate Expectations are addressed as indicated throughout this activity.

B. Student Activity

Suggestions for teacher facilitation are included throughout this activity in italics. Some solutions are included to aid in the flow of the activity.

1. Choose a number. Add three. Multiply by two. Add four. Divide by two. Subtract the original number. What is the result? Repeat this as many times needed to see a pattern in the answers. Describe the pattern. Using deductive methods, prove that your prediction is correct. Students may have to be given the hint to choose x as their original number. Any algebraic method of proving the result would be a deductive method. [CGE4f]

2. The following patterns involve Pythagorean triples (a²+ b² = c²):

n	1	2	3	4	5	6	7	…	21	…	k
a	1	3	5	7	9	11	13
b	0	4	12	24	40	60	84
c	1	5	13	25	41	61	85

a) Verify that each set {a, b, c} satisfies the Pythagorean theorem.

b) For row a find a value for the 21st column. Conjecture a formula to determine the value for the kth column. The 21st value will be 41. The kth entry will have the general form 2k – 1.

c) Look for a pattern in each of the remaining rows. Use this pattern to predict the Pythagorean triplet when n is 21, and determine a formula for the entries in column k. Have you used inductive or deductive reasoning? Explain. Although the values for row a represent a simple arithmetic sequence, the general term for rows b and c are more complex (they are neither arithmetic nor geometric in nature). The general terms in rows b and c are given by 2n(n – 1) and 2n² – 2n + 1, respectively. Some students may need teacher facilitation to reach these expressions. The method of finite differences is preferred, as it is a deductive method for developing a general form. [CGE3c]

d) Prove that the general terms in column n = k satsify the Pythagorean relationship. Is this a deductive or inductive proof? Explain. By using the actual formulas in conjunction with the Pythagorean theorem, the students will have algebraically (deductively) shown that the relationships hold.

Assessment & Evaluation of Student Achievement

The Catholic School Graduate Expectations can be assessed using an appropriate observational checklist or by student self-diagnostic assessment. The teacher may wish to provide the students with a similar activity for use as a summative assessment. The use of mathematical language, the degree of clarity in explanations, and the integration of narrative and mathematical forms of reasoning and justification are all important Communication skills that should be assessed. Knowledge/Understanding could be evaluated using a quiz.

Accommodations

The teacher should ensure that those students with difficulties in understanding concepts be placed into groups in which they can receive support from other students.

Activity 5.2C: What’s So Funny About Peace, Love, And Mathematical Induction?

Time: 1.25 hours

Description

Students are lead through a method of proving algebraic properties known as mathematical induction.

Teaching/Learning Strategies

A. Teacher Facilitation

· The method of mathematical induction outlined below draws parallels to other activities contained in this unit, namely the Follow-Up Skills section in Activity 5.1B: Pick A Tooth, Any Tooth, and Question 2 in Activity 5.2B: Elementary, My Dear Watson. The proof is driven by the construction of a recursive “mechanism,” i.e., if Case n = k is true, then Case n = k + 1 is true. Once this mechanism has been established, all that is left in order to prove the result for all cases is to “start the dominoes falling,” i.e., show that Case n = 1 is true. It is recommended that this be addressed using the steps shown below along with teacher guidance, so that the many intricacies can be discussed at the appropriate time during the process.

· Mathematical induction is “traditionally” approached such that the base case (usually n = 1) is dealt with first. The teacher may wish to mention this to the students, and discuss the possibilities of alternative sequencing in the proof.

· Depending on the abilities of the class members, this may be done individually or in pairs.

· The Catholic School Graduate Expectations are addressed as indicated throughout this activity.

B. Student Activity

Suggestions for teacher facilitation are included throughout this activity in italics. Some solutions are included to aid in the flow of the activity.

Although, by name, it may not seem like it, the method of mathematical induction is actually a deductive method for proving relationships. The premise is analogous to that of dominoes falling upon one another. In competition domino tumbling, strips of dominoes (such as those depicted below) are used to speed up the set up process.

With these strips, one can be assured that if the first domino falls the rest will tumble after. Thus, there is a “mechanism” in place that guarantees that one domino will knock the next one over. Because the strips are identical and can be attached, the last domino on one strip will knock over the first domino on an attached strip. So if an infinite line of these domino strips was constructed, we can be sure that if any of the dominoes has fallen, the next one will be knocked over. All that is needed to tumble the entire (infinitely long) strip is to knock over the first domino. Without visibly verifying it, then, we can be sure that all dominoes will fall.

1. a) Reconsider the example provided in Activity 5.2A, Question 1, given by the equation
1 + 3 + 5 +…+ (2n!1)= n². We can readily check any one particular case (when n = 6, for example, we have 1 + 3 + 5 + 7 + 9 + 11 = 36 = 6²), but how can we verify this equation for all possible values of n?

b) Suppose that the given property is true for some value n = k, so

[1] 1 + 3 + 5 +…+ (2k – 1) = k^2.

Call this the inductive assumption. Why is this only an assumption?

c) In the domino example, to prove that all of our dominoes would fall, we needed a “mechanism” to guarantee that one domino would knock the next one over, so domino k must knock over domino k + 1. We could say that we needed to show that the k + 1st domino would fall, using the kth domino to knock it over. Similarly, for our example, we are going to show that our property holds for n = k + 1, using the property for n = k.

d) We will attempt to prove that, for n = k + 1

[2] 1 + 3 + 5 +…+ (2k – 1)+(2[k + 1] – 1) = (k + 1)²

The teacher may need to review how the last few terms in equation [2] are constructed. How does the series shown in equation [2] compare to that in equation [1]? Why was the term (2k – 1) written if it is not the last in the series? Some students may notice that writing the left hand side in this way explicitly incorporates the left hand side of equation [1]. [CGE3c]

e) Remember we must use our property for n = k (equation [1]) in order to prove our property for
n = k + 1 (equation [2]). Note that the left side of equation [2] contains the entire left side of equation [1]. Using a simple substitution, we make the appropriate replacement, as indicated:

How could this replacement be of use? It eliminates a large, indeterminate portion of the series.

f) After our replacement, we now have k²+ (2[k + 1] – 1).

Expand, collect, then factor to show this expression equals (k +1)² as required to establish that the left side equals the right side in [2]. This proves that the k + 1st case will always be true if the preceding case (the kth case) is true or, stated in reverse, if the present case is true, then the next case will be true. We have thus constructed our “mechanism” to show that one domino will knock over the next. All we have to do is knock over the first domino and we will be guaranteed that they will all fall. For our example, to show that the equation is true for all values, all we have left to do is show that it is true for n = 1.

g) Show that the property holds for the first case, n = 1. Why is the proof incomplete without this step? By showing that the property holds for the first case, then (because of our mechanism) it is true for the next. Similarly, if it’s true for the 2nd case, then the property holds for the 3rd, etc. The teacher may want to discuss the apparent trivial nature of this portion of the proof, i.e., the fact that it is necessary to show it is true for only one known case for the assumption to be true.

h) Essentially there are three parts to this process called mathematical induction:

i) Make the inductive assumption that the relationship is true for n = k.

ii) Use this inductive assumption to prove deductively that the relationship is true for n = k + 1.

iii) Prove the assumption is true for the first possible case (usually when n = 1).

i) Why would this process be considered a deductive proof? A complete explanation should include reference to the fact that since the property is proven for the n = 1 case, the assumption, along with the proof of the n = k + 1 case, shows that it will be true for the n = 2 case. By the same reasoning, since the n = 2 case is true then the n = 3 case must also be true. This argument can be applied to any and all cases, and the property holds for all cases.

2. Prove the relationships found in the Pythagorean triplet exercise (Activity 5.2B, Question 2) using mathematical induction. [CGE4b]

C. Follow-Up Skills (Time: 2.5 hours)

1. The teacher facilitates a discussion of the major steps involved in proof by mathematical induction and the importance of each step.

2. Students are be given time to practise and consolidate skills necessary to fully grasp the intricacies of proof by mathematical induction. Types of questions should include sums of series (with and without sigma notation), inequalities, recursion formulae, and divisibility problems.

Assessment & Evaluation of Student Achievement

The Catholic School Graduate Expectations can be assessed using an appropriate observational checklist or by student self-diagnostic assessment. Due to the nature of this activity, it is recommended that any assessment emphasize Knowledge/Understanding and Communication skills, particularly the use of proper mathematical symbols and conventions. A quiz would be appropriate for this purpose.

Accommodations

Because of the amount of text-based learning in this activity, the teacher should ensure that students with comprehension or communication difficulties be placed into groups in which they can receive support from other students.

Activity 5.3: Ah, Let Me Count The Ways!!!

Time: 2.5 hours

Description

Students explore and investigate additive and multiplicative counting principles using data gathered from their classmates. The principles are developed by the students and consolidated with the help of the teacher. Students are required to apply the principles to a variety of examples, and in addition, generate several of their own applications.

Strand(s) & Learning Expectations

Ontario Catholic School Graduate Expectations

CGE2c - an effective communicator who presents information and ideas clearly and honestly and with sensitivity to others;

CGE4a - a self-directed, responsible, life long learner who demonstrates a confident and positive sense of self and respect for the dignity and welfare of others;

CGE5g - a collaborative contributor who achieves excellence, originality, and integrity in one’s own work and supports these qualities in the work of others;

CGE7b - a responsible citizen who accepts accountability for one’s own actions.

Strand(s): Discrete Mathematics

Overall Expectations

DMV.01 - solve problems, using counting techniques;

PSV.02 - solve problems, using a variety of strategies.

Specific Expectations

DM1.01 - solve problems, using the additive and multiplicative counting principles;

DM1.05 - explain solutions to counting problems with clarity and precision;

PS2.01 - solve problems by effectively combining a variety of problem-solving strategies;

PS2.04 - solve complex problems and present the solutions with clarity and justification.

Planning Notes

· Students are placed in groups of two or three. For larger classes, the teacher may assign the same task to more than one group, or set up more tasks similar to the ones given in Part 1 of the activity.

· Each group is supplied with chart paper that will be used to record and present information gathered from Part 1 of the activity.

· Students can remain in the same groups for Part 2 of the activity.

· Students are to perform Part 3, the Student Assignment component, individually.

Teaching/Learning Strategies

Teacher Facilitation

· The Catholic School Graduate Expectations are addressed as indicated throughout this activity.

· To help set a context and provide motivation for additive counting principles the teacher can provide the following statement for class discussion:

“In a group of 20 strangers it is found that 12 like chocolate ice cream. It is also known that 7 like apple pie. Is it possible that in this group of 20 people that there are exactly 15 who like apple pie or like ice cream?”

· The teacher’s discussion should focus on the gathering and organizing of data. A short introduction to Venn diagrams, used to illustrate the organization of data, is necessary. The teacher must ensure that the students are familiar with the concepts of cardinality of a set, union and intersection of sets, and the notations of n(A), n, and n. The teacher need not formally define these terms, but rather incorporate them into the discussion of Venn diagrams.

· If the teacher chooses to construct additional tasks for Part 1 of the Student Activity, it is advisable to look closely at sets A, B, C, and D in each task to ensure that they have similar relative characteristics (e.g., A and B are disjoint; C and D are not necessarily disjoint, some sets may be null).

· The teacher may wish to add more questions to the tasks in Part 1 of the Student Activity using other combinations of sets A, B, C, and D.

Part 1 – Get To Know Your Classmates

A. Teacher Facilitation

· Each group is to survey all students in the class to determine the number of students that satisfy each of the sets in their assigned task. Alternatively, the students could be surveyed as a group by show of hands. This data is to be recorded on chart paper. The data is also to be illustrated using a Venn diagram on the chart paper. The numbers in each part of the Venn diagram should be clearly labelled. [CGE4a]

Task 1:

A: students with black hair

B: students with blond hair

C: students with glasses

D: students wearing earrings

Task 2:

A: students who have three or more siblings

B: students who are an only child

C: students who eat red meats

D: students who eat fish

Task 3:

A: students who are over 190 cm tall

B: students who are shorter than 175 cm tall

C: students who like math

D: students who like English

Task 4:

A: students who drive their own vehicle

B: students who drive only their parents’ vehicle

C: students who work part-time

D: students who earn $8.00/h or more at a job

· Each group is to answer the given questions for their task and be prepared to present their findings to the class. [CGE2c, CGE5g, CGE7b]

· The teacher should use this part of the activity to summarize and consolidate the appropriate formulas and properties of the additive counting principles. The following concepts may also be addressed at this time: disjoint sets, subsets, complements, DeMorgan’s Laws, null sets, and distributive properties. If the teacher chooses not to address them at this point, they should be addressed in a Follow-Up Skills component.

· There is an opportunity for students to practise and apply all of these skills in Part 3, the student assignment component at the end of this activity.

B. Student Activity

1. Find:

a) n(A)

b) n(B)

c) n(C)

d) n(D)

2. Find n and compare it with n(A)and n(B).

3. Find n and compare it with n(C) and n(D).

4. For any two sets X and Y, generalize a formula for n.

5. For any three sets X, Y, and Z, generalize a formula for n. Use sets B, C, and D in your task to illustrate the formula.

Part 2 – Anyone For Lunch?

A. Teacher Facilitation

· The following problem provides a starting point for discussion on multiplicative counting principle:

“As part of a daily lunch special, the school cafeteria is offering the choice of a tuna, ham, or turkey sandwich, the choice of a soda or milk to drink, and the choice of chocolate pudding, ice cream, or a large cookie for dessert. How many lunch choices does a student have?”

· The teacher can illustrate this with a tree diagram and use it to develop The Fundamental Counting Principle, e.g., for the scenario given above, there are lunch choices.

· The teacher can use any or all of the questions developed by the groups for practise purposes or for an assessment task.

B. Student Activity

Suggestions for teacher facilitation are included throughout this activity in italics.

1. Each group is to develop five practical situations in which The Fundamental Counting Principle and tree diagrams can be applied. For each practical situation, at least five questions (including model solutions) must be developed. Some practical situations include lock combinations, pizza toppings, lotteries, dice games, license plates, telephone numbers and area codes, family trees, computer binary codes, sports lineups, clothing and accessories, simple card games, genetics, etc.

2. Each group will be responsible for presenting one application to the class. [CGE2c, CGE7b]

Part 3 – Student Assignment

Suggestions for teacher facilitation are included throughout this assignment in italics. Some solutions are included to aid in the flow of the activity.

The teacher can use any or all of the following questions for practise and/or assessment purposes:

1. In a survey of 100 students the distribution of students currently enrolled in the Gr. 12U Math courses is: 51 in MCB, 42 in MDM, 30 in MGA, 3 in MDM and MGA, 28 in MGA and MCB, 20 in MCB and MDM, and 2 students in all three courses.

a) Illustrate this with a Venn diagram.

b) How many students study only MCB?

c) How many students do not study MDM?

d) How many students are enrolled in at least one math course?

2. The new hit group, Dukes of Algebraic Deduction (DAD), has just released their new CD containing 13 songs. DAD is hitting the road for their concert tour with MOM (Masters of Math). DAD’s manager wants them to play a set of 4 songs then take a short break. How many different possible sets could they play before their break? Explain. Answers may vary here depending on the students’ interpretation as to whether or not the order of the songs matters.

3. In a newspaper report it states that 1000 people were given a taste test between two sodas. 570 people preferred Cool Mist, 610 preferred Ice Cooler and 150 couldn’t tell the difference and liked both equally. Is this possible? Explain.

4. Until just recently, Ontario licence plates were made up of 3 letters of the alphabet followed by 3 digits. Why was this changed?

5. In many parts of Ontario, new telephone area codes and new 3-digit exchanges have been added in recent years. Why was this done?

6. Use a Venn diagram to illustrate the relationship n. Invent a practical situation that demonstrates this property.

Assessment & Evaluation of Student Achievement

The Catholic School Graduate Expectations can be assessed using an appropriate observational checklist or by student self-diagnostic assessment. Conferencing can assess Knowledge/Understanding of groups and individuals during the activities. Communication skills can be assessed using criteria such as the degree of clarity of explanations, the use of appropriate notation, the use and clarity of Venn diagrams, and the correct use of mathematical language during any one of the oral presentations recommended in the activities. If the student assignment is used, Application skills can be assessed in Questions 1, 2, and 3 (measuring an appropriate use of the multiplicative or additive counting principles, for example). Questions 4, 5, and 6 can be used to assess Thinking/Inquiry/Problem Solving skills. A short quiz can be used to assess Knowledge/Understanding during or after the activity, provided the students have had the opportunity to consolidate the necessary skills.

Accommodations

The teacher should ensure that those students with learning and communication difficulties be placed into groups in which they can receive support from other students.

Activity 5.4: Ping-Pong Or Pong-Ping, Does It Matter?

Time: 3.75 hours

Description

Students use their modelling and critical thinking skills to analyse a sampling of ping-pong balls that enables them to develop an understanding of permutations and combinations. This leads to the development and application of factorial, permutation, and combination notation. These notations are used in a variety of applications including the algebraic manipulation and simplifying of expressions involving permutations, combinations, and factorials. Special properties are investigated with and without calculators and students develop proofs of these special properties and other relationships.

Strand(s) & Learning Expectations

Ontario Catholic School Graduate Expectations

CGE2b - an effective communicator who reads, understands, and uses written materials effectively;

CGE3c - a reflective and creative thinker who thinks reflectively and creatively to evaluate situations and solve problems;

CGE4f - a self-directed, responsible, life long learner who applies effective communication, decision-making, problem-solving, time and resources management skills.

Strand(s): Discrete Mathematics, Proof and Problem Solving

Overall Expectations

DMV.01 - solve problems, using counting techniques;

PSV.02 - solve problems, using a variety of strategies;

PSV.03 - complete significant problem-solving tasks independently.

Specific Expectations

DM1.01 - solve problems, using the additive and multiplicative counting principles;

DM1.02 - express the answers to permutations and combinations problems, using combinatorial symbols (e.g., and P(n, r));

DM1.03 - evaluate expressions involving factorial notations, using appropriate methods (e.g., evaluate mentally, by hand and using a calculator);

DM1.04 - solve problems involving permutations and combinations, including problems that require the consideration of cases

DM1.05 - explain solutions to counting problems with clarity and precision;

PS2.01 - solve problems by effectively combining a variety of problem-solving strategies;

PS2.03 - use technology effectively in making and testing conjectures;

PS2.04 - solve complex problems and present the solutions with clarity and justification;

PS3.01 - solve problems of significance, working independently, as individuals and in small groups.

Prior Knowledge & Skills

· Students should be familiar with tree diagrams and the Fundamental Counting Principle, i.e., multiplicative counting techniques.

· Factoring skills, particularly in the simplifying of polynomial and rational expressions, are required for this activity.

Planning Notes

· For Part 1 of the activity, the teacher should have numbered ping-pong balls or different coloured multi-link cubes (or pieces of paper) available for the students to actually perform the activity.

Teaching/Learning Strategies

A. Teacher Facilitation

Students should do this activity individually. A thorough understanding of the concepts of Part 1 is necessary for success in the subsequent parts of the activity.

It may be necessary for the teacher to help consolidate the students’ understanding of tree diagrams and multiplicative counting principles.

The Catholic School Graduate Expectations are addressed as indicated throughout this activity.

B. Student Activity

Suggestions for teacher facilitation are included throughout this activity in italics. Some solutions are included to aid in the flow of the activity.

Part 1 – Ping-Pong

1. There are four ping-pong balls (numbered 1 to 4) in a box. You are to pick out three balls (one at a time without replacement) at random and record the result, e.g., 4-1-3 may be one result. List all of the possible results. How many are there?

2. With the same four ping-pong balls, you are to pick out three balls simultaneously, this time with no regard for the order, i.e., 4-1-3 would be the same as 1-4-3 and 3-1-4, etc. List all of the possible results. How many are there? Compare your answer with Question 1. What is the relationship? Explain. [CGE3c]

3. Repeat Questions 1 and 2 using five numbered ping-pong balls instead of four. [CGE2b]

4. Suppose now there were eight ping-pong balls, and three balls were to be picked out of the box without replacement. Find the total number of results:

a) if the order matters, i.e., the balls were picked out one at a time and recorded in order;

b) if the order does not matter, i.e., the balls were picked out simultaneously.

5. Selections in which order matters (as in Question 1) are referred to as permutations. Selections in which order does not matter (as in Question 2) are referred to as combinations. Use these definitions to determine if the following are permutations or combinations. Justify (but do not evaluate).

a) Four students are to be selected from a school of 750 students as the school’s prime minister, deputy prime minister, treasurer, and secretary.

b) A committee of three students is to be selected to represent their school’s 800 students on a community environmental focus group.

c) In the card game of bridge, four players are each dealt 13 cards from the standard playing deck of 52 cards. Students could classify this problem in either way depending on students’ interpretation – number of hands for a player (combination) or if the order of the players is taken into account (permutation).

d) If there are 12 players on a school’s basketball team, how many different starting lineups of 5 players could a coach make? Students could answer either way depending on whether or not designated positions (centre, guard, etc.) are given to each player.

Part 2 – Pong-Ping

The teacher should consolidate the concepts and skills from Part 1 before progressing on to Part 2. Many questions in Part 2 refer back to questions in Part 1. Due to the nature of the complexity of the subject material in this activity, the teacher should closely monitor the students’ progress, and should offer facilitation and intervention wherever necessary.

Let us revisit the ping-pong ball scenario given in Part 1 to answer the following questions:

1. If there are four numbered ping-pong balls in a box and you are to pick out four balls (one at a time without replacement) and record the results, how many different possibilities could you get?

2. If you did the same with five ping-pong balls, how many results are possible? With 10 ping-pong balls? With 25 ping-pong balls? With 100 ping-pong balls?

3. Using a calculator to evaluate each example in Question 2, you may experience some difficulties. Why? At this point, the teacher may wish to facilitate a short class discussion focusing on the need for a special notation to represent these calculations. The teacher can use the following as a guide in order to formally define factorial notation:

“In the past few years, we’ve used notation to represent very large or small numbers (like 2⁵⁰ or
3 ´ 10^-4) that are either too cumbersome to write and/or too large or small to evaluate. Similarly, there is special notation that can be used to represent the answers to the questions above. The solution to Question 1, for example, using the Fundamental Counting Principle, is . But can also be represented by the factorial notation 4!, which is read as “4 factorial.” In a similar manner, 10! (or 10 factorial) has a value of .”

The teacher should spend time with the students evaluating factorials with a scientific calculator.

4. Explain any limitations or problems in evaluating factorials with your scientific calculator. Factorials are defined for whole numbers only. There is an upper limit (around n = 70), after which the numbers become too large for the calculator to compute.

5. Complete the following table (use a calculator only where necessary):

n
4
5	…	….
6
7
8
30
100

6. Use the table above to help you determine a general formula for and . [CGE4f]

7. Are there any restrictions on the value of n in these formulas? Explain. n must be a whole number greater than or equal to 3 and confirm by using a calculator.

8. Refer back again to Questions 1, 2, and 3 from Part 1. Put your answers in an appropriate factorial form, similar to the form shown in Question 6. [CGE4f]

9. At times, even factorial notation may be somewhat cumbersome when dealing with permutations and combinations. For these cases, other special notations can be used:

· P(n, k) is used for a permutation, and represents the total number of results when k items are selected (with order) from n items.

P(n, k) is used for… n terms.

Therefore P(n, k) = n(n – 1) (n – 2) … (n – k + 1). Since this expression would often require input of many factors when using a calculator, we can re-express the formula to require fewer calculator entries.

· C(n, k) or (more commonly) = is used for a combination, and represents the total number of results when k items are selected with no regard to order from n items.
Another notation used for permutations and combinations (and seen on several brands of scientific calculators) is _nP_k and _nC_k, respectively.

10. At this point, the teacher should provide some time for the students to evaluate a variety of permutations and combinations with their scientific calculators.

11. Explain any limitations or problems in evaluating permutations and combinations with your scientific calculator. n and k Î W, such that n ³ k.

12. Invent a problem that would yield the following results: [CGE3c]

a) P(12, 3)

13. Go back to Question 5 from Part 1 and evaluate the answers by using the appropriate permutation or combination formula and factorial notation to simplify. (Excessively large answers can be left in factorial notation.) The solutions are as follows (parts (c) and (d) have been interpreted as combinations):

a) P(750, 4) = ; b) =; c) =; d) =

The teacher should give students ample time to practise the algebraic simplifying (i.e., without a calculator) of a variety of permutations and combinations
(e.g., =).

14. Even with all of the notations and approaches illustrated thus far, some problems are more complex still. Cases may need to be considered, and the addition counting principle may be necessary. The following is an example: The digits 0, 1, 4, 5, and 6 are to be used to generate 3-digit even numbers (no digit can be repeated).

a) Why is P(5, 3) not the correct answer?

b) Recall the characteristics of Venn diagrams and additive counting principles to develop cases that can be analysed separately to find the total number of 3-digit even numbers that can be generated. One case is where 0 is the last digit and a second case is where 0 is not the last digit; then add the results of these two cases.

Part 3 – Student Assessment

To aid in the evaluation process, some solutions and teacher facilitation have been included in italics.

The following questions involve the algebraic manipulation and simplifying of relationships involving factorials, permutations, and combinations, using concepts and results from previous parts of this activity. They could be assigned as homework and the solutions shared. Similar questions could be posed on a test.

1. Simplify:

a) P(n, n)	b) P(n, 1)	c) P(n, 0)	d) P(n, k)

e)	f)	g)	h)

2. What is the relationship between Questions 1d and 1h? Prove this relationship algebraically.

3. Simplify the expression a!(a²+ 3a + 2) . The solution is (a + 2)!.

4. Determine a if = n³ + 6n² + 11n + 6. The value of a is 3.

5. Prove (n + 1)! – n! = n!n.

6. Solve for n if 5P(n, 3) = 24. The value of n is 8.

7. How many different lottery ticket number combinations are available in Lotto 6/49? (A customer must pick exactly six numbers between 1 and 49 inclusive). There are combinations possible.

8. How many seating arrangements are there for 12 players on the bench prior to a basketball game? There are P(12, 12) = 12! arrangements possible.

9. How many seating arrangements are there for 12 players on the bench prior to a basketball game if the coach insists that the starting centre and the starting point guard must each sit beside him? There are P(2, 1) P(10, 10) possibilities.

10. A committee of four students is to be chosen to attend a conference on conflict resolution. The committee must have the same number of boys and girls.

a) How many committees could be chosen from a group of 4 girls and 5 boys? The solution is . Students may have to list and count first in order to arrive at the result.

b) From a group of n₁ girls and n₂ boys, a committee of m₁ girls and m₂ boys is to be chosen. How many such committees could be chosen? There are possibilities. Are there any restrictions on n₁, n₂, m₁, and m₂?

C. Follow-Up Skills

Time: 1 hour

The teacher should supplement this activity with suitable problems. A wide variety of questions should be assigned, including:

· simplifying and evaluating expressions involving permutations, combinations, and/or factorials;

· solving relationships involving permutations, combinations, and/or factorials;

· applying permutations, combinations and/or factorials to a variety of contextual problems;

· applications that involve the consideration of cases;

Assessment & Evaluation of Student Achievement

The Catholic School Graduate Expectations can be assessed using an appropriate observational checklist or by student self-diagnostic assessment. A short quiz can be used to measure Knowledge/Understanding during or after the activity, provided the students have had a chance to consolidate skills. The majority of questions in Parts 1 and 2 can be used to assess Knowledge/Understanding by conferencing with individual students. Communication skills can be assessed in any question in Parts 1 and 2 that ask students to explain or justify. Question 6 of Part 2 can be used to assess Thinking/Inquiry/Problem Solving skills. Question 14 of Part 2 can be used to assess Application skills. The Student Assignment section has a variety of questions addressing all four categories of the Achievement Chart, as denoted before each question. The teacher can use any or all of these questions for assessment purposes.

Activity 5.5: Summative Assessment

Time: 2 hours

Description

A comprehensive, balanced summative assessment addressing all four Achievement Chart categories should be administered at the end of this unit. Students must be provided with the opportunity to demonstrate their ability to apply the skills and knowledge acquired in this unit. During this assessment, the skills developed in the combinatorics activities will be assessed and extended in the context of arranging letters in words. The first part of this assessment involves the development of techniques for dealing with arrangements of elements in a set with repeated or indistinguishable elements. The second part of the combinatorics section is a paper-and-pencil task.

Strand(s) & Learning Expectations

Ontario Catholic School Graduate Expectations

CGE3c - a reflective and creative thinker who thinks reflectively and creatively to evaluate situations and solve problems;

CGE4b - a self-directed, responsible, life long learner who demonstrates flexibility and adaptability;

CGE4f - a self-directed, responsible, life long learner who applies effective communication, decision making, problem-solving, time and resource management skills.

Strand(s): Proof and Problem Solving; Discrete Mathematics

Overall Expectations

PSV.02 - solve problems, using a variety of strategies;

PSV.03 - complete significant problem-solving tasks independently;

DMV.01 - solve problems, using counting techniques;

DMV.02 - prove results, using mathematical induction.

Specific Expectations

PS2.01 - solve problems by effectively combining a variety of problem-solving strategies;

PS2.04 - solve complex problems and present the solutions with clarity and justification;

PS3.01 - solve problems of significance, working independently, as individuals and in small groups;

DM1.01 - solve problems, using the additive and multiplicative counting principles;

DM1.02 - express the answers to permutation and combination problems, using standard combinatorial symbols;

DM1.03 - evaluate expressions involving factorial notation, using appropriate;

DM1.05 - explain solutions to counting problems with clarity and precision;

DM2.01 - demonstrate an understanding of the principle of mathematical induction;

DM2.02 - use sigma notation to represent a series or the sum of a series;

DM2.03 - prove the formulas for the sums of series, using mathematical induction.

Prior Knowledge & Skills

· Students must possess a comprehensive knowledge of the concepts introduced and extended throughout this unit.

Planning Notes

· Students work in groups to propose an algebraic solution to the problem of arranging n elements given that k elements are identical. Students then explore the problem individually, using a student activity to guide them through an investigation. At the conclusion of the activity, students regroup and review their original proposal based on their individual experiences.

· Provide an acetate marker and sheet for each group.

· The teacher may wish to provide the students with letter tiles to use as manipulatives for some of the questions.

Teaching/Learning Strategies

A. Teacher Facilitation

· The teacher may want to clarify that a set refers to a collection of elements (like the letters T, C,
and A), and an arrangement refers to the order in which these elements are placed (e.g., CAT and ACT are different arrangements of letters from the same group).

· Each task in this assessment is preceded by the skill categories that would be most applicable to the given task ([K/U] indicates Knowledge/Understanding, [T/I/PS] indicates Thinking/Inquiry/Problem Solving, [C] indicates Communication, and [A] indicates Application).

· The Catholic School Graduate Expectations are addressed as indicated throughout this activity.

B. Student Activity

To aid in the evaluation process, some solutions and teacher facilitation have been included in italics.

Part 1 – Group Assessment

i) Discussion and Conjecture

The teacher should begin the activity by posing the question:

“How many different arrangements of the letters in the words MATH, MATT and POPPY are possible? Develop a systematic way to determine the number of distinct arrangements of n letters given that k of them are identical.”

Students should be given time to discuss and develop a method for solving the problem. Students should be instructed to record their ideas in their journals. [CGE4f]

ii) Investigation

Once the students have had an opportunity to fully explore the problem, they should use the following guide to develop a more formal understanding of how to determine the number of arrangements when there are repeated elements. It is recommended that students work individually within their groups for this part of the activity.

1. [K/U, C] Consider the four letters that make up the word MATH. Write down all of the possible 4-letter arrangements of these letters. Explain a systematic way of doing this. Verify the number of arrangements. Students should be able to do this using factorial notation.

2. [K/U, C] Now consider the word MATT. Write down all of the possible distinct 4-letter arrangements of these letters. How does the number of arrangements of these letters compare with the number of arrangements for the letters of the word MATH? How will your systematic method used in Question 1 have to be altered here (if at all)? Students should realize that the Ts are non-distinct and thus their order with respect to each other is not important. [CGE3c]

3. [K/U, T/I/PS, C] Using factorial notation, find the number of arrangements of the letters of the word FORTY. By replacing the F, R, and T with the letter P, we obtain the word POPPY. Write down all of the possible different 5-letter arrangements of the letters of the word POPPY. Compare the number of arrangements of 5 distinct elements (FORTY) to the number of arrangements of five elements with three indistinguishable or repeated elements (POPPY). Explain any relationship between these two values. Some students may conjecture that the second is found by dividing the first by 6 or 3!.

4. [T/I/PS, A] Write down the different 5-letter arrangements of the letters of the fictional word POPPP. Compare this number of arrangements to that of the word FORTY.

5. [A] Compare the results of Questions 3 and 4 using the following table:

k	3	4
Number of arrangements of five distinct elements
Number of arrangements of five elements with k indistinguishable elements
Quotient of number of arrangements with distinct elements divided by number of arrangements with k indistinguishable elements
Factorial form of quotient

6. [C, A] Make a general statement about the number of arrangements of n elements of which k of them are repeated or indistinguishable. The number of arrangements is n! ¸ k!. Use this to determine the number of arrangements of six elements of which four of them are repeated. [CGE3c, CGE4f]

7. [K/U, T/I/PS] How many different arrangements of the letters of the word COOCOO are possible? Write them out. Can you extend the generalization made in Question 6 to include the possibility that there may be more than one element that is repeated? The number of arrangements of the letters of the word COOCOO is . In general, the number of arrangements is given by , where a and b represent the number of times each letter is repeated. [CGE4f]

8. [K/U, C] Summarize your results on the acetate sheet. On the acetate, answer the following questions:

a) How many distinct arrangements of the letters of the word MINIMUM are possible?

b) How many distinct arrangements of the letters of the word MINIMUM are possible if each arrangement must start with an M? In this case, one of the Ms can be taken out and fixed as the first letter. The question then reduces to the arrangement of the letters in the word INIMUM, which has 6 letters, two sets of two which are indistinguishable.
The answer, then, is .

iii) Revision and Conclusion

At the conclusion of the Student Activity section, the students should return to their groups, where they will then consolidate their findings by revisiting and revising their original journal entries. [CGE4b]

Part 2 – Individual Assessment

1. [K/U, T/I/PS] Use mathematical induction to prove the following statements:

a) 1² + 2² + 3² + … + n² = , n Î N.

b) n³ – n is divisible by 6 for n Î N.

c) , n Î N.

d) If n is a natural number, prove that is a natural number.

e) , for n Î 2, n > N.

f) Given x > 0, (1 + x)ⁿ > 1 + nx + nx² for n > 2, n Î N.

g) .

h) .

i) Given t_k = 2^k! 1 for k Î N, show that for all n Î N, n ³ 2, t_n = 3t_n_-1– 2t_n_-2.

j) 2ⁿ⁺³ < (n + 3)!

2. [K/U, T/I/PS, A] Conjecture a formula for the sum of the first n terms of each the following series, then verify these conjectures using mathematical induction: [CGE3c]

b) 1 + 5 + 9 + 13 + …

For the following questions, students may attempt to use cases, then add the results of each case. While this is correct each problem (with the exception of Question 7), can be solved without cases. Problems that need to be solved using cases are explored in more detail in Unit 6 – Applications of Counting Techniques.

3. [K/U] Given the words GRADE, CREATION, and HYPERBOLA, how many arrangements can be made of the letters of each word if:

a) all of the letters are used?

b) only four of the letters are used at any one time?

4. [K/U, A] In how many ways can the letters of the word VECTOR be arranged if each arrangement must start with V and end with R, and:

a) all six letters are used? Write out each arrangement. Since the V and R are fixed, this is just a problem of arranging 4 letters, i.e., There will be 4! Arrangements.

b) only four letters are used? Write out each arrangement.

5. a) [K/U, A] How many groups of three letters can be formed from the letters in the word MATRIX? Write them out.

b) [C] Does the problem in part (a) represent a permutation or a combination? Explain. Since the order doesn’t matter, this is a combination.

c) [K/U] In how many ways can any of the 3-letter groups from part (a) be arranged?

d) [C, A] How many 3-letter words can be made from the letters of the word MATRIX? Explain your answer.

6. [T/I/PS, C] How many 4-letter words can be made from the letters of the word PULLEYS? Explain your answer. This question requires the use of cases, e.g., (Case 1: all letters distinct, Case 2: two letters indistinguishable – LL), and addresses expectation DM1.04, which is not included in this unit. Students should be evaluated solely on their problem-solving skills (expectations PSV.02 and PSV.03). [CGE3c, CGE4f]

7. [K/U, C, A] There is a clever way to show that for any number b (except 0), b⁰= 1. To evaluate the expression b^a ¸ b^a using our exponent laws, we need only subtract the exponents,
so b^a ¸ b^a = b^{a -
a} = b⁰. But we also know that b^a ¸ b^a = . Thus, by transitivity, b⁰ = 1.

a) Use a similar method to illustrate that 0! = 1.

b) If 0! = 1!, does this mean that 0 = 1? Explain.

9. [C, A] Keeping permutations and combinations in mind, develop some strategies for making Internet passwords more secure. There are more possible arrangements of characters if a password is longer and contains both letters and numbers. Also, a password is more likely to be secure if it bears no resemblance to a “real” word. [CGE4f]

Assessment & Evaluation of Student Achievement

In this summative assessment, several opportunities exist for the evaluation of all of the knowledge and skill categories. Criteria to be assessed in the activity might include: the ability to determine the equation of the formulas for combinatoric problems (Knowledge/Understanding; Thinking/Inquiry/Problem Solving); the formulation and defence of a hypothesis (Thinking/Inquiry/Problem Solving); the ability to predict results (Application).

In the group and individual assessments, criteria might include: the use of limited information to make generalized statements regarding combinatoric problems (Thinking/Inquiry/Problem Solving); the creation of a model to represent data (Thinking/Inquiry/Problem Solving); the accuracy of calculations (Knowledge/Understanding); the use and analysis of information to answer indirect questions (Thinking/Inquiry/Problem Solving; Application); the proper use of mathematical vocabulary, symbols, and conventions in the justification of conclusions (Communication).

Accommodations

Additional time should be provided for those students with comprehension and communication difficulties.

Overview | Unit 3 | Course Profiles Main Menu