Skip to content
Tutorials Center
My learning

Topics

Lesson 63 of 68 ยท Practice and Review

Common Mistakes and Pitfalls

Learn the classic errors in counting, implication, double counting, floating point and induction, and use short Python experiments to catch each one.

Discrete mathematics has a reputation for being tricky, but most mistakes come from a small set of habits. People miscount by one, pick a permutation formula when the problem wanted a combination, read "if P then Q" as "if Q then P", count the same object twice, trust a rounded decimal, or start an induction proof from the wrong place. The good news is that every one of these can be caught by a quick experiment.

This lesson walks through the most common traps, shows each one failing in Python, and gives you a short checklist to apply to your own work. The cure is always the same: test your claim on small cases before you believe it.

Six classic traps

Off by one Fence posts and inclusive ranges.
Order or not Permutation versus combination.
Backwards if Converse is not the same statement.
1 / 2

Mistake 1: off-by-one errors in counting

How many integers are there from 7 to 20 inclusive? The tempting answer is 20 โˆ’ 7 = 13, but the correct count is 14, because both ends are included. The general rule for integers a to b inclusive is b โˆ’ a + 1. A related trap is the fence-post problem: a fence with 10 sections has 11 posts, not 10.

Python itself is a source of confusion because range(a, b) excludes b, so len(range(7, 20)) is 13 and len(range(7, 21)) is 14. Likewise a sum written as โˆ‘ from i = 1 to n has n terms, but a loop for i in range(1, n) runs only n โˆ’ 1 times.

Python Counting inclusive ranges and fence posts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The multiples of 3 between 10 and 100 number 30. The formula is the number of multiples up to 100 minus the number up to 9, which is the neat way to count "up to b but not up to a โˆ’ 1" and avoids fence-post slips. When in doubt, list the first few and last few elements by hand.

Mistake 2: permutation or combination?

The choice comes down to one question: does order matter? Choosing a president, vice president and treasurer from 10 people is a permutation, because the same three people in different roles are different outcomes: 10ยท9ยท8 = 720. Choosing a committee of three is a combination: C(10, 3) = 120, and each committee corresponds to 3! = 6 orderings that should count once.

A second question is whether repetition is allowed. The four standard cases are:

  • ordered, no repetition: P(n, k) = n!/(n โˆ’ k)!
  • unordered, no repetition: C(n, k)
  • ordered, repetition: nแต
  • unordered, repetition: C(n + k โˆ’ 1, k)
Python Four ways to choose 3 from 10

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The four answers are 720, 120, 1000 and 220. Notice 720 / 120 = 6 = 3!, the relationship that connects the first two. If you ever get a combination count larger than the permutation count of the same problem, you have made a mistake.

Mistake 3: misreading implication

"If it rains, the ground is wet" does not mean "if the ground is wet, it rained". The sprinkler may have been on. The reversed statement is the converse, and it is a different claim. The statement that is always equivalent to the original is the contrapositive: "if the ground is not wet, it did not rain".

A second trap is vacuous truth. P โ†’ Q is true whenever P is false, so "if 2 is odd, then 2 > 100" is a true statement. This is not a trick: it is what makes "every element of the empty set is positive" true, and what makes proofs about all items of a possibly empty list work.

The safest way to check is a truth table. Python makes that a few lines.

Python Implication, converse and contrapositive

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The table's third and fourth columns disagree on the rows (True, False) and (False, True), while the first and last columns match on every row. The last line prints True False: all over an empty list is true, any is false, exactly as the logic predicts.

A frequent error when negating "for all x, P(x)" is to write "for all x, not P(x)". The correct negation is "there exists x with not P(x)". The same flip happens for "there exists", which becomes "for all ... not". Test negations on a small finite domain with all() and any() before you trust them.

Mistake 4: double counting

You count objects by describing them, and trouble starts when two different descriptions give the same object. A classic example: how many five-card hands contain at least one ace? A tempting method is to choose one ace first (4 ways) and then fill the other four cards from the remaining 51: 4 ยท C(51, 4) = 999,600. But a hand with two aces is counted twice (once for each ace you could have "chosen first"), and a hand with three aces three times.

There are two clean fixes. One is complement counting: hands with no ace number C(48, 5), so hands with at least one ace are C(52, 5) โˆ’ C(48, 5). The other is inclusion-exclusion, which corrects overlaps explicitly.

Python Aces in a poker hand: wrong method versus right

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The wrong method gives 999,600, while the correct number of hands with at least one ace is 886,656, an overcount of 112,944. The small-deck experiment shows the same effect where you can verify by enumeration: the truth is 369, the naive method says 495 and the complement method says 369.

The lesson is general. Whenever a counting argument starts with "first choose one of ..." ask: could the same final object be reached by two different first choices? If yes, you are double counting.

Mistake 5: floating point instead of exact arithmetic

Discrete mathematics asks for exact answers. Floats are approximations, and they betray you in surprising places: sums that should be exactly 1, equality tests, and large factorials. Python's int and fractions.Fraction are exact, and they are the right tools for counting and probability.

Python Floats versus exact integers and fractions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first line prints False 0.30000000000000004, while the fraction comparison is True. Dividing 2โตยณ + 3 by 2 with / rounds to a float, so int(n / 2) gives 4503599627370498, one more than the exact floor division n // 2 = 4503599627370497. The binomial coefficient C(100, 50) computed through floats is 100891344545564202071714955264, wrong from the 16th digit on (the exact value ends in ...193334812497256), so the equality test prints False. Prefer math.comb and integer // everywhere.

Another trap in the same family: math.sqrt and **0.5 for perfect-square tests or primality bounds. Use math.isqrt(n), which returns an exact integer square root.

Mistake 6: starting induction in the wrong place

An induction proof has two parts: a base case and an inductive step. Skipping the base case is the infamous error. The "proof" that all horses have the same color has an inductive step that looks fine in general, but it breaks when going from 1 horse to 2, so the chain never starts. A more ordinary slip is choosing the wrong base: the claim "2โฟ > nยฒ" is false for n = 3 and 4 but true from n = 5 on, so the base case must be n = 5, and the inductive step has to be valid from there.

Before attempting a proof, check the claim numerically. A numeric test cannot prove a statement for all n, but it can quickly reveal where a statement starts to hold, or that it never does.

Python Finding where a claim starts to hold

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The inequality 2โฟ > nยฒ holds for n = 0 and 1, fails at n = 2, 3 and 4 (the output shows [2, 3, 4]), and holds again from n = 5 on. That is why a proof must start at n = 5. The polynomial nยฒ + n + 41 produces primes for n = 0 to 39, yet n = 40 gives 1681 = 41ยฒ, which is not prime. No number of successful cases proves a general claim, and a pattern that holds for 40 values can still fail. The last line checks the algebra of an inductive step for many k, which is useful for catching typos but is not itself the proof.

A checklist for your own work

Keep this list next to you when solving problems.

  1. Test small cases first. Count by brute force for n = 1, 2, 3 and compare with your formula.
  2. State the model. Order or no order? Repetition or none? Inclusive or exclusive endpoints?
  3. Check for double counting. Can one object arise from two different constructions?
  4. Write the converse and contrapositive out loud when a statement has the form "if ... then ...".
  5. Use exact arithmetic: integers, //, math.comb, Fraction, math.isqrt.
  6. For induction, name the base case and the smallest n for which the step works. Do they overlap?
  7. Sanity-check the size. A probability must lie between 0 and 1; a count of subsets cannot exceed 2โฟ.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many integers are there from 15 to 40 inclusive?

    Inclusive counting uses b - a + 1 = 40 - 15 + 1 = 26.
  2. 2. A club chooses a president, a secretary and a treasurer (three different roles) from 8 members. Which count applies?

    Different roles mean different outcomes for the same three people, so order matters: 8 * 7 * 6 = 336.
  3. 3. Which statement is always logically equivalent to 'if P then Q'?

    The contrapositive is equivalent. The converse and the inverse are different statements.
  4. 4. Why does '4 * C(51, 4)' overcount hands with at least one ace?

    A hand with two aces arises from two different 'first ace' choices, so it is counted twice; three aces give three counts, and so on.
  5. 5. Why is 'the claim holds for n = 1 to 40' not a proof?

    n^2 + n + 41 is prime for 40 values and fails at n = 40. A proof must cover every n, for example by induction.

Summary

  • Count inclusive ranges as b โˆ’ a + 1, and remember that range(a, b) excludes b.
  • Ask whether order matters and whether repetition is allowed, then pick one of the four standard formulas; verify with itertools.
  • The converse of an implication is not equivalent to it; the contrapositive is. Implications with a false premise are vacuously true.
  • Beware counting methods that start by "choosing one special element first": they often double count. Complement counting and inclusion-exclusion fix this.
  • Use integers, //, math.comb and Fraction for exact answers, and math.isqrt for square roots.
  • An induction proof needs the right base case and a step that is valid from that base; check small cases numerically first.

Next: Exercises: Logic, Sets and Proofs.