Mathematics Benchmarks, Grades K-12

Secondary Mathematics Benchmarks Progressions, Grades 7–12: Discrete Mathematics (D)

Discrete mathematics, sometimes called finite mathematics, can be thought of as the science of counting, arrangements, and algorithms. It offers a plethora of concrete, practical problems (e.g., fair apportionment, searching algorithms, error-correction methods) and a wealth of subtle problems whose statements are deceptively simple but whose solutions provide significant challenge. While events in the physical world are most often modeled by continuous mathematics (i.e., the calculus and prerequisite topics in algebra, geometry, and trigonometry), the increasingly important world of computers, information technology, and logistics employs a different type of mathematics. New approaches and applications require the use of discrete processes, many of which have not traditionally been included in core high school courses. To be well prepared for the future, all students need to understand the concepts and applications of this important area of mathematics.

D.A.1 Sets and Boolean algebra

a. Know the concepts of sets, elements, empty set, relations (e.g., belong to), and subsets, and use them to represent relationships among objects and sets of objects.

Recognize and use different methods to define sets (lists, defining property).

b. Perform operations on sets: union, intersection, complement.

Example: Use Boolean search techniques to refine online bibliographic searches.

c. Create and interpret Venn diagrams to solve problems.

d. Identify whether a given set is finite or infinite; give examples of both finite and infinite sets.

D.B.1 Permutations and combinations

a. Determine the number of ways events can occur using permutations, combinations, and other systematic counting methods.

A permutation is a rearrangement of distinct items in which their order matters; a combination is a selection of a given number of distinct items from a larger number without regard to their arrangement (i.e., in which their order does not matter).

Know and apply organized counting techniques such as the Fundamental Counting Principle.
The Fundamental Counting Principle is a way of determining the number of ways a sequence of events can take place. If there are n ways of choosing one thing and m ways of choosing a second after the first has been chosen, then the Fundamental Counting Principle says that the total number of choice patterns is n⋅m.
Examples: How many different license plates can be formed with two letters and three numerals? If the letters had to come first, how many letters would be needed to create at least as many different license plate numbers? How many different subsets are possible for a set having six elements?
Distinguish between situations that do not permit replacement and situations that do permit replacement.
Examples: How many different four-digit numbers can be formed if the first digit must be non-zero and each digit may be used only once? How many are possible if the first digit must be non-zero but digits can be used any number of times?
Distinguish between situations where order matters and situations where it does not; select and apply appropriate means of computing the number of possible arrangements of the items in each case.

b. Interpret and simplify expressions involving factorial notation.

Examples: Interpret 6! as the product 6 · 5 · 4 · 3 · 2 · 1; recognize that 15 factorial over 12 factorial = 15 · 14 · 13 = 2,730.

D.B.2 Discrete graphs

a. Construct and interpret decision trees.

A tree is a connected graph containing no closed loops (cycles).

Represent and analyze possible outcomes of independent events (e.g., repeated tossing of a coin, or throwing dice) using tree diagrams.
Tree diagrams can also be used to analyze games such as tic-tac-toe or Nim or simply to organize outcomes.

Task related to this benchmark: Rock, Paper, Scissors

b. Create and interpret network graphs.

A graph is a collection of points (nodes) and the lines (edges) that connect some subset of those points; a cycle on a graph is a closed loop created by a subset of edges. A directed graph is one with one-way arrows as edges.

Use graphs to diagram and study social and organizational networks.
Examples: Determine the shortest route for recycling trucks; schedule when contestants play each other in a tournament; illustrate all possible travel routes that include four cities; interpret a directed graph to determine the result of a tournament.

c. Construct and interpret flow charts.

D.B.3 Iteration and recursion

a. Analyze and interpret relationships represented iteratively and recursively.

Example: Recognize that the sequence defined by "First term = 5; each term after the first is six more than the preceding term" is the sequence whose first seven terms are 5, 11, 17, 23, 29, 35, and 41.

Analyze the sequences produced by recursive calculations using spreadsheets.
Example: The result of repeatedly squaring a number between – 1 and 1 appears to approach zero, while the result of repeatedly squaring a number less than –1 or greater than 1 appears to continue to increase; determine empirically how many steps are needed to produce 4-digit accuracy in square roots by iterating the operations divide and average.
Describe the factorial function or the Fibonacci sequence recursively.

b. Generate and describe sequences having specific characteristics.

Generate a relatively small number of terms by hand and use calculators and spreadsheets effectively to extend the sequence.
Describe arithmetic sequences recursively.
Arithmetic sequences are those in which each term differs from its preceding term by a constant difference. To describe an arithmetic sequence, both the starting term and the constant difference must be specified.
Describe geometric sequences recursively.
Geometric sequences are those in which each term is a constant multiple of the term that precedes it. To describe a geometric sequence, both the starting term and the constant multiplier (often called the common ratio) must be specified.
Given an irrational number expressed using rational exponents or radicals, find increasing and decreasing sequences that converge to that number and show that the first terms of these sequences satisfy the right inequalities.
Example:
1 < 1.4 < 1.41 < 1.414 < . . . < < 1.415 < 1.42 < 1.5 < 2 since 1² = 1 < (1.4)² = 1.96 < (1.41)² = 1.9881 < (1.414)² = 1.999396 < . . . < ()² = 2 < . . . < (1.415)² = 2.002225 < (1.42)² = 2.0164 < (1.5)² = 2.25 < 2² = 4
Describe other regular patterns of growth recursively.
Examples: The factorial function; the Fibonacci sequence.

c. Demonstrate the effect of compound interest, decay, or growth using iteration.

Display the effect of iteration using a calculator or spreadsheet.
Examples: Enter the amount of a loan, the monthly interest rate, and the monthly payment in a spreadsheet. The formula (loan amount) · (1+interest rate) − (monthly payment) gives the amount remaining monthly on the loan at the end of the first month, and the iterative "fill down" command will show the amount remaining on the loan at the end of each successive month; a similar process using past data about the yearly percent increase of college tuition and annual inflation rate will provide an estimate of the cost of college for a newborn in current dollar equivalents.
Identify the diminishing effect of increasing the number of times per year that interest is compounded and relate this to the notion of instantaneous compounding.

D.C.1 Algorithms

a. Identify and give examples of simple algorithms.

An algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task that, given an initial state, will terminate in a defined end-state. Recipes and assembly instructions are everyday examples of algorithms.

Analyze and compare simple computational algorithms.
Examples: Write the prime factorization for a large composite number; determine the least common multiple for two positive integers; identify and compare mental strategies for computing the total cost of several objects.
Analyze and apply the iterative steps in standard base-10 algorithms for addition and multiplication of numbers.

b. Analyze and apply algorithms for searching, for sorting, and for solving optimization problems.

Identify and apply algorithms for searching, such as sequential and binary.
Describe and compare simple algorithms for sorting, such as bubble sort, quick sort, and bin sort.
Example: Compare strategies for alphabetizing a long list of words; describe a process for systematically solving the Tower of Hanoi problem.
Know and apply simple optimization algorithms.
Example: Use a vertex-edge graph (network diagram) to determine the shortest path for accomplishing some task.

D.C.2 Mathematical reasoning

a. Use correct mathematical notation, terminology, syntax, and logic.

Explain reasoning in both oral and written forms.

b. Distinguish between inductive and deductive reasoning.

Inductive reasoning should be clearly distinguished from the deductive mathematical reasoning involved in mathematical induction.

Identify inductive reasoning as central to the scientific method and deductive reasoning as characteristic of mathematics.
Inductive reasoning is based on observed patterns and can be used in mathematics to generate conjectures, after which deductive reasoning can be used to show that the conjectures are true in all circumstances. Inductive reasoning cannot prove propositions; valid conclusions and proof require deduction.
Explain and illustrate the importance of generalization in mathematics and its relationship to inductive and deductive reasoning.
Example: No number of specific instances that illustrate the commutative property of addition can show that the property holds true for all real numbers, whereas a + b = b + a (a and b real) is an axiom that includes all such cases.

c. Explain and illustrate the role of definitions, conjectures, theorems, proofs, and counterexamples in mathematical reasoning.

Identify and give examples of definitions, conjectures, theorems, proofs, and counterexamples.
Recognize flaws or gaps in the reasoning used to support an argument.
Demonstrate through example or explanation how indirect reasoning can be used to establish a claim.

Tasks related to this benchmark: Archeological Similarity, Common Differences

d. Make, test, and confirm or refute conjectures using a variety of methods.

Use inductive reasoning to formulate conjectures and propose generalizations.
Construct simple logical arguments and proofs; determine simple counterexamples.

Task related to this benchmark: Regional Triangles

D.C.3 Propositional logic

a. Use and interpret relational conjunctions ("and," "or," "not"), terms of causation ("if . . . then") and equivalence ("if and only if").

Distinguish between the common uses of such terms in everyday language and their use in mathematics.
Relate and apply these operations to situations involving sets.

b. Describe logical statements using terms such as assumption, hypothesis, conclusion, converse, and contrapositive.

c. Recognize and avoid flawed reasoning, including, but not limited to, "Since A → B, therefore B → A."

d. Recognize syllogisms, tautologies and circular reasoning and use them to assess the validity of an argument.

D.E.1 Quantitative applications

a. Identify and apply the quantitative issues underlying voting, elections, and apportionment.

Compare features of common methods of voting (e.g., majority, plurality, runoff) and describe how their results can vary.
Identify, compare, and apply methods of apportionment.
Example: Devise a student government where the seats are fairly apportioned among all constituencies.

b. Know and use methods of fair division and negotiation strategies.

D.E.2 Sequences and series

a. Know and use subscript notation to represent the general term of a sequence and summation notation to represent partial sums of a sequence.

b. Derive and apply the formulas for the general term of arithmetic and geometric sequence.

c. Derive and apply formulas to calculate sums of finite arithmetic and geometric series.

d. Derive and apply formulas to calculate sums of infinite geometric series whose common ratio r is in the interval (–1, 1).

e. Model, analyze, and solve problems using sequences and series.

Examples: Determine the amount of interest paid over five years of a loan; determine the age of a skeleton using carbon dating; determine the cumulative relative frequency in an arithmetic or geometric growth situation.

D.E.3 Recursive equations

a. Convert the recursive model for discrete linear growth (A₁ is given and A_n+1 = A_n + d for n > 1, d a constant difference) to a closed linear form (A_n = a+d(n – 1)).

This model generates an arithmetic sequence.

b. Convert the recursive model of discrete population growth (P₁ is given and P_n+1 = rP_n for n > 1, r a constant growth rate) to a closed exponential form (P_n = ar^n-1).

This model generates a geometric sequence.

c. Analyze, define, and calculate sequences that are neither arithmetic nor geometric using recursive methods.

It is often much clearer and less difficult to represent sequences recursively than in closed form.

D.E.4 Digital codes

a. Interpret common digital codes (e.g., zip codes, universal product codes (UPC), and ISBNs on books) and identify their special characteristics.

b. Understand, evaluate, and compare how error detection and error correction are accomplished in different common codes.

Examples: Codes read by scanners; transmission of digital pictures over noisy channels; playing a scratched CD recording.

Know the meaning of a check digit and how it is calculated.

c. Identify characteristics of common forms of data compression (e.g., mp3, jpeg, and gif).

d. Analyze the concepts underlying public-key encryption and digital signatures that enable messages to be transmitted securely.

One method uses the fact that factoring a big number is much more difficult than creating one by multiplying two primes.

D.E.5 Mathematical induction

a. Analyze and describe how mathematical induction rests on the definition of whole numbers and explain how proof by mathematical induction establishes a proposition.

Mathematical induction is a unique logical principle used to establish the truth of an infinite sequence of statements that are indexed by positive integers, that is, true for all positive integers k. Formally, the principle states that if p(1) is true, and if, for each integer k, p(k + 1) is true whenever p(k) is true, then p(n) is true for all n.

b. Identify common theorems that can be proved by mathematical induction and explain why this method of proof works for these theorems.

c. Use mathematical induction to prove simple propositions.

Example: Prove that for every positive integer n, 1 + 2 + 3 + 4 + . . . + n = n(n + 1)/2.

D.E.6 Proof by contradiction

a. Analyze and explain how proof by contradiction can be used to establish a proposition.

Proof by contradiction is an indirect method of reasoning that shows that a conclusion cannot be false rather than showing directly that it is true. Typically, a proof by contradiction begins by assuming that the desired conclusion is not true and then uses correct reasoning to reach an absurd conclusion (such as that 1 = 0). For this reason, the method is often known by its Latin name: reductio ad absurdum.

b. Identify examples of theorems for which an indirect argument is useful and assess whether an indirect argument is useful to prove a particular theorem.

Example: Establishing that square root of 2 is irrational can be done using an indirect argument.

c. Use an indirect argument to prove a result.

Examples: Any non-zero rational multiple of an irrational number is irrational; the sum of a rational number and an irrational number is irrational.