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\).


No Comments

Post a Comment