MATC44H3 Chap.7 Induction and the Frobenius Coin Problem
Induction and the Frobenius Coin Problem
The course's statement of induction
The induction slide frames the method in its strong form: statements P(k) indexed by k are proved by checking a few starting cases, as many as the problem needs, and then showing that the truth of every case up to n forces the case n + 1. The first example is the formula for the sum 0 + 1 + ⋯ + n, which needs one base case.
The second is the Frobenius coin problem, phrased in the lecture with boxes of chicken nuggets, which needs several.
Why coin problems need a run of base cases
To show that an amount n + 1 can be paid with packs whose smallest size is s, the natural step removes one small pack and appeals to the amount n + 1 − s.
That amount lies s places back, so the step is valid only after s consecutive amounts have been checked by hand. The practice solutions check four amounts for boxes of 4, 6 and 9, and six amounts for packages of 6, 7 and 11, before writing the step.
They also prove that the claimed largest impossible amount really is impossible, by trying every possible number of the larger packs.
Strong induction beyond coins
The river-crossing problem in the practice set moves a group of size k + 1 by reusing crossings for groups of size k, k − 2 and k − 1, so three base cases are verified first.
The first assignment asks students to guess a closed form for a sum from its first few values and then prove the guess by induction, which is the other common shape of an induction question.
What to practise
Coin and package problems with two or three sizes, the sum formula, and closed forms guessed from small values are the shapes to rehearse, with the base cases and the hypothesis written out in full.
What this chapter covers
- 01
Induction with several base cases
- 02
The sum of the first n integers
- 03
Frobenius coin problem and the largest gap
- 04
Base runs as long as the smallest pack
- 05
Strong induction reaching several steps back
- 06
Guessing and proving a closed form
Worked example · free
Packs of 3 and 7
- 111 is impossible: subtracting 0 or 7 leaves 11 or 4, neither divisible by 3.
- 2Base run: 12 = 3 × 4, 13 = 3 × 2 + 7, 14 = 7 × 2.
- 2Step: for n ≥ 14, if every amount from 12 to n can be paid, so can n + 1 = (n − 2) + 3.
Key terms
- Base Case
- A base case is a statement verified directly so that an inductive step can build on it.
- Inductive Hypothesis
- The inductive hypothesis is the assumption that the statement holds for the earlier values used in the step.
- Frobenius Number
- The Frobenius number of a set of pack sizes is the largest amount that cannot be made exactly from them.
- Closed Form
- A closed form is an expression for a sum or sequence without a summation sign or an ellipsis.
Induction and the Frobenius Coin Problem FAQ
How many base cases does a coin problem need?
As many as the size of the pack the inductive step removes, usually the smallest pack. If the step writes n + 1 as an amount s less plus one pack of size s, it reaches s places back, so s consecutive amounts must be verified by hand first.
How do I prove that an amount is impossible?
Suppose it can be written with nonnegative numbers of each pack, bound the number of the largest packs, and try each possibility. For each, check whether what remains can be made from the smaller packs. When every case fails, the amount is impossible. The practice solutions argue exactly this way.
What is the difference between induction and strong induction?
Ordinary induction uses only the statement for n to prove it for n + 1. Strong induction may use every earlier statement. The course's statement of induction is already the strong form, and coin and river-crossing problems need it because their steps reach several places back.
How should I find a closed form before proving it?
Compute the first few values exactly, look for a pattern in the numerators and denominators or in the differences, and write a guess. Then check it on one more value before starting the induction, because a proof of a wrong guess will fail at the step.
Exam move
Prove the sum formula and one coin result from memory, writing the base cases and the hypothesis in full. Then take two pack sizes of your own, find the largest impossible amount by listing small amounts, and prove the result in three parts: the gap, the base run and the step.
Working through Induction and the Frobenius Coin Problem in MATC44H3? Sia is AskSia’s AI Mathematics tutor — ask any MATC44H3 Induction and the Frobenius Coin Problem question and get a clear, step-by-step explanation grounded in how MATC44H3 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
