Category Archives: Solutions

Exercise 2.2.6

March 16, 2020 Issa Rice 6 Comments

Exercise statement

Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m{{+}\!{+}})$ is true, then $P(m)$ is true. Suppose that $P(n)$ is also true. Prove that $P(m)$ is true for all natural numbers $m \leq n$ ; this is known as the principle of backwards induction.

Hints

Apply induction to the variable $n$ .
For the statement to prove via induction, use the following: if $P(n)$ is true, then $P(m)$ is true for all $m \leq n$ .

How to think about the exercise

For this kind of abstract exercise, it helps to have an example in mind. Unfortunately, I am not aware of a convincing application of backwards induction. Pete L. Clark’s notes use a very similar result (which he calls upward-downward induction) to prove the AM-GM inequality, but he also says “It is not every day that one proves a result by Upward-Downward Induction”.

However, we can still play around with this a little. Suppose $P(4)$ is true. Then $P(3)$ is also true, which means that $P(2)$ is also true, which means that $P(1)$ is also true, which finally means that $P(0)$ is true. In other words, we have shown that $P(m)$ is true for all $m \leq 4$ , which is exactly what backwards induction claims. What if $P(5)$ is true? Then $P(4)$ is true. We already showed that if $P(4)$ is true, then $P(m)$ is true for all $m \leq 4$ . This means that we have now shown that $P(m)$ is true for all $m \leq 5$ .

I also like to translate these kinds of problems into formal logic notation, because otherwise it’s difficult to see with mathematical English where the parentheses are supposed to be. This exercise is asking us to prove the following: if $\forall m(P(m{{+}\!{+}}) \implies P(m)) \wedge P(n)$ then $\forall m (m \leq n\implies P(m))$ . For this kind of exercise, I encourage you to work with the formal logic notation as you’re solving the exercise, but make sure to convert back to mathematical English when writing up the exercise.

As with some induction problems, one thing you need to do is to decide on the statement you want to prove via induction. One mistake you could make is to show that $P(n)$ is true for all $n$ . This is not what you want to do! In fact, given just the information in the exercise statement, it is impossible to show that $P(n)$ is true for all $n$ . Another possibility is to use the statement “If $P(n)$ is true and $P(m{{+}\!{+}})$ implies $P(m)$ for all $m$ , then $P(m)$ is true for all $m \leq n$ .” This will work. However, it turns out that including the “ $P(m{{+}\!{+}})$ implies $P(m)$ for all $m$ ” part is not necessary — you can just assume it once at the start of the exercise, so that the actual induction step will be slightly cleaner.

Model solution 1

Let $P$ be a property pertaining to the natural numbers such that whenever $P(m{{+}\!{+}})$ is true, $P(m)$ is true.

Let $Q(n)$ be the following statement: if $P(n)$ is true, then $P(m)$ is true for all $m \leq n$ .

We shall show that $Q(n)$ is true for all $n$ using induction. For the base case, we must show $Q(0)$ . So suppose that $P(0)$ is true. We want to show that $P(m)$ is true for all $m \leq 0$ . By definition of inequality (definition 2.2.11), $m \leq 0$ means that $0 = m+a$ for some natural number $a$ . By corollary 2.2.9, we have $m=0$ . In other words, $m \leq 0$ implies $m=0$ , so showing that $P(m)$ for all $m \leq 0$ is equivalent to showing $P(0)$ , which we already know. This completes the base case.

Now suppose $Q(n)$ is true. We must show that $Q(n{{+}\!{+}})$ is true. By definition of $Q$ , $Q(n{{+}\!{+}})$ is the statement “if $P(n{{+}\!{+}})$ is true, then $P(m)$ is true for all $m \leq n{{+}\!{+}}$ ”, so suppose that $P(n{{+}\!{+}})$ is true. We need to show that $P(m)$ is true for all $m \leq n{{+}\!{+}}$ . We know that whenever $P(m{{+}\!{+}})$ is true, $P(m)$ is true, so for $m=n$ in particular this means that if $P(n{{+}\!{+}})$ is true then $P(n)$ is true. Since $P(n{{+}\!{+}})$ is true, we see that $P(n)$ is true. By the induction hypothesis we thus have $P(m)$ for all $m \leq n$ . Now let $m \leq n{{+}\!{+}}$ . We want to show that $P(m)$ is true. If we can show that $m \leq n$ or $m=n{{+}\!{+}}$ , then we will be done, because in either case we have already shown that $P(m)$ is true. To show that $m \leq n$ or $m=n{{+}\!{+}}$ , we will show that $m\ne n{{+}\!{+}}$ implies $m \leq n$ . Suppose $m \ne n{{+}\!{+}}$ . This means $m < n{{+}\!{+}}$ by definition 2.2.11. By proposition 2.2.12(e), we have $m{{+}\!{+}} \leq n{{+}\!{+}}$ , i.e. $m+1 \leq n+1$ . By proposition 2.2.12(d) this means $m\leq n$ as required. This closes the induction.

Now let $n$ be a natural number, and suppose $P(n)$ is true. By our work above, we know that $Q(n)$ is true. This means that $P(m)$ is true for all natural numbers $m \leq n$ as required.

Model solution 2

Thanks to Charlene for this solution.

Let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m{{+}\!{+}})$ is true, then $P(m)$ is true. Suppose that $P(n)$ is also true. We want to show that $P(m)$ is true for all $m \leq n$ .

Let $Q(k)$ be the statement: for all natural numbers $m$ , if $m+k = n$ then $P(m)$ is true. (The intuition here is that $Q(k)$ is basically the statement that $P(n-k)$ is true. But we can’t say $P(n-k)$ since we haven’t defined subtraction yet! So that’s why we do some first-order logic trickery to say what we want given our current tools. We know that $P(n-0)$ is true by assumption, and the rule that whenever $P(m{{+}\!{+}})$ is true, then $P(m)$ is true, means that we can go from $P(n-0)$ to $P(n-1)$ , from $P(n-1)$ to $P(n-2)$ , and so on, all the way to $P(n-n)$ .)

We will show using induction that $Q(k)$ is true for all natural numbers $k$ . For the base case, $k=0$ , we want to show that for all $m$ , if $m+0=n$ then $P(m)$ is true. So let $m$ be a number, and suppose $m+0=n$ . Then we have $m=m+0=n$ . Since we assumed $P(n)$ is true, this means $P(m)$ is true as required.

Now suppose inductively that $Q(k)$ is true. We want to show that $Q(k{{+}\!{+}})$ is true. That is, we want to show that for all $m$ , if $m+(k{{+}\!{+}}) = n$ then $P(m)$ . So let $m$ be given, and suppose $m+(k{{+}\!{+}})=n$ . Thus we have $(m{{+}\!{+}}) + k = n$ . By our inductive hypothesis $Q(k)$ , this means that $P(m{{+}\!{+}})$ is true. We also know that whenever $P(m{{+}\!{+}})$ is true, then $P(m)$ is true. Thus $P(m)$ is true. This shows that $Q(k{{+}\!{+}})$ is true, and closes our induction.

Now suppose $m \leq n$ . We want to show that $P(m)$ is true. But $m \leq n$ means that there exists some $k$ such that $m+k=n$ . By what we showed above, we know that $Q(k)$ is true. And $Q(k)$ says that if $m+k=n$ , then $P(m)$ is true, as required.

Solutions

Exercise 2.2.2

March 16, 2020 Issa Rice 33 Comments

Exercise statement

Prove Lemma 2.2.10.

Lemma 2.2.10. Let $a$ be a positive number. Then there exists exactly one natural number $b$ such that $b{{+}\!{+}} = a$ .

Hints

Use induction.

How to think about the exercise

This exercise asks us to show that it makes sense to talk about the predecessor of a positive number. For instance, the predecessor of $3$ is $2$ . Why is there a hypothesis that $a$ must be a positive number? Because by axiom 2.3 the number $0$ does not have a predecessor (within the set of natural numbers).

This exercise is almost a standard induction exercise, but not quite. The one subtlety is that the inductive hypothesis is never used. This might seem suspicious to you, but it’s actually harmless.

Model solution

Let $P(a)$ be the statement “If $a$ is positive, then there is a unique natural number $b$ such that $b{{+}\!{+}} = a$ .” We shall induct on $a$ . The base case is vacuously true, since $0$ is not a positive number (definition 2.2.7).

Now suppose inductively that $P(a)$ is true. We must show that $P(a{{+}\!{+}})$ is true. To show that $P(a{{+}\!{+}})$ is true, it suffices to show that there is a unique number $b$ such that $b{{+}\!{+}} = a{{+}\!{+}}$ (this is because given statements $p,q$ , if $q$ is true, then $p \implies q$ is also true no matter what $p$ says). To do this, we must show two things: (1) there is a natural number $b$ such that $b{{+}\!{+}} = a{{+}\!{+}}$ ; (2) if $c$ is a natural number such that $c{{+}\!{+}} = a{{+}\!{+}}$ , then $c=b$ . To show (1), let $b:=a$ . Then indeed we have $b{{+}\!{+}} = a{{+}\!{+}}$ . To show (2), let $c$ be a natural number such that $c{{+}\!{+}} = a{{+}\!{+}}$ . Then by axiom 2.4, we see that $c=a$ . But we also know $b=a$ , so $c=b$ as required. This closes the induction.

Solutions

Exercise 2.2.1

March 16, 2020 Issa Rice 8 Comments

Exercise statement

Prove Proposition 2.2.5.

Proposition 2.2.5 (Addition is associative). For any natural numbers $a,b,c$ , we have $(a+b)+c = a + (b+c)$ .

Hints

Fix two of the variables and induct on the third.

How to think about the exercise

This is a simple induction exercise; it just tests your ability to write an induction proof and make use of the definition of addition. This sort of exercise requires no thinking (once you get the hang of things): at each step, you just do the next obvious thing.

Model solution

We shall fix $b,c$ and induct on $a$ . For the base case, we want to show $(0+b)+c = 0 + (b+c)$ . By definition of addition, $0+b = b$ , so $(0+b)+c = b+c$ . Again by definition of addition, $0 + (b+c) = b+c$ . Thus, $(0+b)+c = 0 + (b+c)$ as required.

Now suppose inductively that $(a+b)+c = a + (b+c)$ . We wish to show that $((a{{+}\!{+}})+b)+c = (a{{+}\!{+}}) + (b+c)$ . By definition of addition, $((a{{+}\!{+}}) + b) + c = ((a + b){{+}\!{+}}) + c = ((a+b) + c){{+}\!{+}}$ . Similarly, $(a{{+}\!{+}}) + (b+c) = (a + (b+c)){{+}\!{+}}$ ; by the inductive hypothesis, this is $((a+b)+c){{+}\!{+}}$ . In other words, both $((a{{+}\!{+}}) + b)+c$ and $(a{{+}\!{+}}) + (b+c)$ are equal to $((a+b)+c){{+}\!{+}}$ . This closes the induction.

Solutions

Exercise 2.3.4

March 15, 2020 Issa Rice 4 Comments

Exercise statement

Prove the identity $(a+b)^2 = a^2 + 2ab + b^2$ for all natural numbers $a,b$ .

Hints

Use Proposition 2.3.4 and Lemma 2.3.2.

How to think about the exercise

This exercise is basically just an application of all of the propositions and lemmas that appeared in this section (Section 2.3).

Exercises like this one test your ability to rigorously apply definitions and results. For each step, you want to cite the result which justifies it.

Model solution

Let $a,b$ be natural numbers. By definition of exponentiation (Definition 2.3.11), $(a+b)^2 = (a+b)^1 \times (a+b) = (a+b)(a+b)$ . By the distributive law (Proposition 2.3.4), we have $(a+b)(a+b) = (a+b)a + (a+b)b$ . By the distributive law again, $(a+b)a = aa + ba$ ; by the definition of exponentiation and commutativity of multiplication (Lemma 2.3.2) this is just $a^2 + ab$ . Similarly, by the distributive law, $(a+b)b = ab + bb = ab + b^2$ . Summarizing everything so far, we have $(a+b)^2 = a^2 + ab + ab + b^2$ . It now suffices to show that $ab + ab = 2ab$ . By the associativity of multiplication and definition of multiplication, $2ab = 2\times(ab) = (1\times (ab)) + ab = ab+ab$ .

Solutions

Exercise 6.3.3

March 15, 2020 Issa Rice 6 Comments

Exercise statement

Prove Proposition 6.3.8.

Proposition 6.3.8 (Monotone bounded sequences converge). Let $(a_n)_{n=1}^\infty$ be a sequence of real numbers which has some finite upper bound $M \in \mathbf R$ , and which is also increasing (i.e., $a_{n+1} \geq a_n$ for all $n \geq m$ ). Then $(a_n)_{n=m}^\infty$ is convergent, and in fact

$\displaystyle \lim_{n\to\infty} a_n = \sup(a_n)_{n=m}^\infty \leq M$

Hints

Use proposition 6.3.6.

How to think about the exercise

I should think of more things to say for this exercise. I remember having a really difficult time with it when I first encountered it, but now it seems so simple.

Model solution

Call the least upper bound of the sequence $\alpha := \sup(a_n)_{n=m}^\infty$ . Since the sequence is bounded above, $\alpha$ is a real number. Now, $\alpha$ is the least upper bound while $M$ is merely an upper bound, so we have $\alpha \leq M$ (proposition 6.3.6). To complete the proof, we must show $\lim_{n\to\infty} a_n = \alpha$ . Let $\varepsilon > 0$ , and observe that $\alpha - \varepsilon$ cannot be an upper bound, since it is less than the least upper bound; in other words, if $\alpha - \varepsilon$ were an upper bound, then we have found a smaller upper bound than $\alpha$ , which contradicts the fact that $\alpha$ is the least upper bound. Thus there exists $N \geq m$ such that $a_N > \alpha - \varepsilon$ (again, this is an application of proposition 6.3.6). Since the sequence is increasing, we have $a_n \geq a_N$ for all $n \geq N$ . Thus

$\displaystyle \alpha + \varepsilon > \alpha \geq a_n \geq a_N > \alpha - \varepsilon$

for all $n \geq N$ . This means $\varepsilon > a_n - \alpha > -\varepsilon$ so $|a_n - \alpha| < \varepsilon$ . Since $\varepsilon > 0$ was arbitrary, this shows that $\lim_{n\to\infty} a_n = \alpha$ as desired.

Solutions

Exercise 5.4.8

March 15, 2020 Issa Rice 18 Comments

Exercise statement

Let $(a_n)_{n=1}^\infty$ be a Cauchy sequence of rationals, and let $x$ be a real number. Show that if $a_n \leq x$ for all $n\geq 1$ , then $\mathrm{LIM}_{n\to\infty} a_n \leq x$ . Similarly, show that if $a_n \geq x$ for all $n \geq 1$ , then $\mathrm{LIM}_{n\to\infty} a_n \geq x$ .

Hints

Do a proof by contradiction.
Use Proposition 5.4.14.
Use Corollary 5.4.10 or Proposition 5.4.9.

How to think about the exercise

This exercise is a pretty straightforward application of the propositions/corollaries mentioned in the hint, so there is not much to discuss!

Model solution

Suppose $a_n \leq x$ for all $n \geq 1$ , and suppose for sake of contradiction that $\mathrm{LIM}_{n\to\infty} a_n > x$ . By Proposition 5.4.14, there exists a rational number $q$ such that $\mathrm{LIM}_{n\to\infty} a_n > q > x$ . Consider the Cauchy sequence $(q)_{n=1}^\infty$ . Since $a_n \leq x < q$ for all $n \geq 1$ , Corollary 5.4.10 tells us that $\mathrm{LIM}_{n\to\infty} a_n \leq \mathrm{LIM}_{n\to\infty} q =q$ . But now we have both $\mathrm{LIM}_{n\to\infty} a_n \leq q$ and $\mathrm{LIM}_{n\to\infty} a_n > q$ , a contradiction.