Patterns, recurrence and induction: Arithmetic, Round 1

1 Learn

You will be able to

Compute terms of a sequence from a recurrence and from a formula.
Say why checking cases does not prove a formula, and what a proof adds.
Write the base case and the step of an induction proof with a reason beside each line of algebra.
Tell linear growth from exponential growth and state the limits of a growth model.

LibraryDiscrete Mathematics and Graphs: Counting, Relations and Networks · Induction and recurrencesThe sum formula proved by induction, with its base case and step, and the Fibonacci recurrence.2 min glance · 6 min
LibraryDiscrete Mathematics and Graphs: Counting, Relations and Networks · Counting without overcountingCounting unordered pairs by multiplying and then dividing by 2, the method behind the handshake count.2 min glance · 6 min
LibraryProof and Precise Reasoning: From Arguments to Theorems · What a proof is, and is notWhy cases can refute a claim about all n but cannot prove it.2 min glance · 6 min
LibraryThe Seven Liberal Arts, Hands-On: Logic, Proof and the Quadrivium · The quadrivium in practiceA short program tests a conjecture before you try to prove it: testing refutes quickly, but never proves.2 min glance · 7 min
LibraryAlgebra: The Skills That Carry Everything · Write the reason beside the stepThe habit of writing the reason next to each line of algebra, which an induction step needs.2 min glance · 6 min
LibraryAlgebra: The Skills That Carry Everything · Exponential growth modelsP(t) = P0 x b^t, what each parameter means, and the limits of the model.2 min glance · 6 min
LibraryMathematics for Better Decisions · Tier 2: compoundingLinear growth adds the same amount each period, compounding multiplies, and the Rule of 72.2 min glance · 5 min

2 Practise

Answer each card from memory, then grade yourself honestly. The cards join your review deck and come back just before you would forget them.

explain
Why does a successful run of Dijkstra's algorithm on one example not show that the algorithm is correct?

Show answer
A run shows only what happened on that input. Correctness needs a proof, and Dijkstra's proof, by an invariant, covers only non-negative edge weights. With negative weights it can fail, so a test that happens to pass proves nothing about the general case.
apply
A club of 6 people must choose two co-chairs, and the roles are interchangeable. How many pairs are possible, and why is 6 x 5 the wrong count?

Show answer
There are C(6, 2) = 15 pairs. Multiplying 6 x 5 = 30 counts ordered pairs, so each unordered pair is counted twice and you must divide by 2.
apply
A classmate checks a formula for n = 1, 2, 3 and 4 and concludes it holds for every positive integer n. Why is that not a proof, and which proof form on the page is built to cover every n?

Show answer
Checking particular cases can refute a universal claim but cannot establish it; the next case could fail, as "every odd number is prime" fails at 9. Induction can cover every n: prove a base case, then prove that if the formula holds for n, it holds for n + 1.
connect
This page says the counterexample habit underlies the testing habit in 'Hypotheses, Predictions and Tests'. What asymmetry drives that habit, and how does it shape the way you test an explanation?

Show answer
One valid counterexample refutes a universal claim, while checking some cases cannot prove it. So you ask "what would refute this?" and design tests whose result could show the explanation wrong, writing the prediction down before you look.
apply
A student finds that a formula gives a prime for every whole number from 0 to 20 and is ready to claim it always does. What does the page advise, and what does its Euler example show?

Show answer
Passing cases is not proof: testing refutes quickly but never proves, so keep testing and seek a proof. Euler's n squared plus n plus 41 gives a prime for every n from 0 to 39, yet n = 40 gives 1681, which is 41 squared.
recall
State the compounding formula and the Rule of 72.

Show answer
A quantity growing by r per period is multiplied by (1 + r)^n after n periods. The Rule of 72 approximates doubling time as 72 divided by the percentage rate; at 6 percent that is about 12 periods (the exact value is 11.9).
connect
The page calls a growth model such as P(t) = P0 * b^t 'a claim with a domain of validity', a theme developed in 'Quantitative Reasoning with Stated Assumptions'. What should you state about such a model?

Show answer
State what each parameter means: P0 is the starting amount, b the growth factor per time unit, and t has units that must match b. Then state its limits: real populations, loans and epidemics grow exponentially only for a while, until resources, rules and saturation bend the curve.

3 Prove it: the mastery check

5 questions drawn from a pool of 12. The pass mark is 80%. There is no time limit, and you can retake it with new questions; your best result counts.

4 Prove it: the performance task

Guess, test, prove

Add up the first n odd numbers for n = 1 to 8 (1, then 1 + 3, then 1 + 3 + 5, and so on) and put the sums in a table. State a conjecture: a formula in n for the sum of the first n odd numbers. Then prove it for every n from 1 upward by induction. Write the base case, the assumption for n, the step to n + 1 and the conclusion, with a reason beside every line of algebra. Finish with two sentences: what the table showed, and what only the proof can show.

What to hand in: One page: the table, the conjecture, the induction proof with a reason beside each line of algebra, and the two closing sentences.

Saved only in this browser. To keep a copy, download it or export your progress.

5 Discuss: the seminar

Read the text, then think, write or talk through the question with someone. There is no answer key: the aim is a better question.

Arithmetic · Round 1

Nicomachus of Gerasa, Introduction to Arithmetic, translated by Martin Luther D'Ooge (Macmillan, 1926), Book I, chapters 7 to 13Chapter 7 divides number into even and odd. Chapters 8 to 10 divide the even. Chapters 11 to 13 divide the odd into the prime and incomposite, the secondary and composite, and the kind that is composite in itself but prime and incomposite relative to another. Chapter 13 also describes the sieve of Eratosthenes and a test by repeated subtraction for whether two odd numbers have a common measure. D'Ooge's translation was published in 1926, so it entered the public domain in the United States on 1 January 2022. This Zenodo record holds a full PDF scan of the 1926 volume. Cite by book and chapter, not by page.
Euclid, Elements, Book VII (David Joyce's online edition, Clark University), Definitions 1 to 16; Propositions 1 and 2Definitions 11 to 14 define prime, relatively prime, composite and relatively composite numbers by what measures them. Propositions 1 and 2 are linked from the same page. Proposition 2 finds the greatest common measure of two numbers by repeated subtraction; Elements X.2 applies the same idea to magnitudes.

Euclid calls a prime a number 'measured by a unit alone' (Book VII, Definition 11), while Nicomachus calls it 'prime and incomposite' and files it among the odd numbers (I.11). What does each way of defining a prime make you notice, and what does each hide?

On Euclid's Definition 11, does the number 2 count as prime? Where would Nicomachus put it, given that he sorts primes among the odd numbers?
Nicomachus describes a sieve (I.13) that separates primes from composites by a procedure. Does knowing how to find primes tell you what a prime is?
In VII.1 and VII.2 Euclid subtracts the smaller number from the larger again and again. What does he assume about what it means for one number to 'measure' another?

Keep notes on the seminars page →

Patterns, recurrence and induction