# September 22, 2016

We continued working on the problems from last week’s proof strategies handout.

• We solved problem 4 using classical induction on the number of vertices of the polygon. When reducing the case of $$n+1$$ vertices to the case of $$n$$, we had to be careful. In particular, making sure that we still had three colors was a bit of a fine point.
• We observed that problem 4 might also be done using strong induction. We did not finish the details of the argument, since it did not appear to be easier.
• The theme of the day was becoming induction, so we worked on problem 8. We observed that having the equality for $$m$$ allowed us to prove it for $$2m$$, and thus from the hypothesis we get it for all powers of 2 by induction. To finish, we noticed that we could prove the equality for $$n=3$$ assuming the case $$n=4$$, and more generally we could prove the case of $$n-1$$ from the case for $$n$$.
• There was some discussion about what functions $$f : \mathbb{R} \to \mathbb{R}$$ can satisfy the equality in problem 8. We noticed that linear functions ($$f(x) = ax$$ for a real constant $$a$$) and affine functions  ($$f(x)= ax+b$$ for real constants $$a,b$$) do satisfy it, and we looked at the geometrical interpretation of the equality. For those who have taken linear algebra, we also pointed out that any $$\mathbb{Q}$$-linear function $$\mathbb{R} \to \mathbb{R}$$ satisfies the equality, and there are such $$\mathbb{Q}$$-linear functions which are not $$\mathbb{R}$$-linear (though we cannot write them explicitly, we can only prove their existence using arguments that depend on the Axiom of Choice).

Today’s nuggets of wisdom:

Arguments by induction come in several different flavors, including:

• Classical: We assume the statement holds for $$n$$ , and prove it for $$n+1$$.
• Strong: We assume the statement holds for $$1,2,\dotsc,n$$ , and prove it for $$n+1$$.
• Back and forth: This one has two parts:
• Using classical induction, we prove the statement for an increasing sequence of natural numbers (say, powers of 2).
• We assume the statement holds for $$n$$ , and prove it for $$n-1$$.