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