Proofs of Universal Statements: Mathematical Induction · Base of Induction

Lesson 4

Nikolai Chukhin · Alexander S. Kulikov

Let us prove that any integer \(m \ge 8\) can be represented as a sum of threes and fives, by induction on \(m\). First, let's verify that we can change \(m=8,9,10\): \[8=5+3,\ 9=3+3+3,\ 10=5+5.\] This means we can also change \(m=11,12,13\): \[11=8+3,\ 12=9+3,\ 13=10+3,\] and we already know how to change \(8,9,10\). Then, we can also change \(m=14,15,16\), because \[14=11+3,\ 15=12+3,\ 16=13+3.\] And so on. As we see, the base of induction here considers three cases instead of one, and the step is treated slightly differently (instead of \(m \to m+1\) we use \(m \to m+3\)).

The corresponding reasoning can easily be transformed into a recursive algorithm. And this is not surprising: induction and recursion are almost the same thing.

base_cases = {8: [5, 3], 9: [3, 3, 3], 10: [5, 5]}


def change(amount):
    assert amount >= 8
    if amount in base_cases:
        return base_cases[amount]
    return change(amount - 3) + [3]


print(change(28))

[5, 5, 3, 3, 3, 3, 3, 3]

For the curious 🤓
The code can be made faster and more compact (though a bit more cryptic at the same time) by eliminating recursion and list copying. 
def change(a):
    return ([5, 3], [3, 3, 3], [5, 5])[(a - 8) % 3] + [3] * ((a - 8) // 3)

For the curious 🤓
The generalization of the coin problem is known as the Frobenius problem. Let \(a_{1}, \dotsc, a_{n} \in \mathbb{Z}_{>0}\). Define the set \[S=\{a_{1}x_{1}+\dotsb+a_{n}x_{n} \colon x_{1}, \dotsc, x_{n} \in \mathbb{Z}_{\ge 0}\}.\] What is the structure of \(S\)? For example, for \(a_{1}=3, a_{2}=5\), \(S=\{ 0, 3, 5, 6\} \cup \mathbb{Z}_{\ge 8}\). Note that it is the condition of non-negativity of the coefficients \(x_{1}, \dotsc, x_{n}\) that makes the problem difficult: if \(x_{1}, \dotsc, x_{n}\) could take any integer values, then \(S\) would coincide with the set of all integers that are divisible by the greatest common divisor of the numbers \(a_{1}, \dotsc, a_{n}\).

The largest number \(g(a_{1}, \dotsc, a_{n}) \in \mathbb{Z}\) that is not contained in \(S\) is called the Frobenius number. There are many natural questions about this quantity.

  1. Does the number \(g(a_{1}, \dotsc, a_{n})\) always exist?
  2. Is there a formula for \(g(a_{1}, \dotsc, a_{n})\) (in the case when it exists)?
  3. If the number \(g(a_{1}, \dotsc, a_{n})\) exists, how many numbers from \([g(a_{1}, \dotsc, a_{n})]\) fall into \(S\)?
We know the answer to the first question, but we can fully answer the second and third questions only for \(n=2\). For \(n>2\) the problem of finding the Frobenius number is already NP-hard.