Update for 4/13: Induction

On Thursday and Friday, I did problems from the second section of Putnam and Beyond, induction. The essence of a proof by induction is the following:

You want to show a statement is true for all positive integers n. (Or nonnegative integers, or integers starting from 3, etc.)

You first show the statement is true for 1 (or whatever you are starting with, this is called the base case), and then show if it is true for some n, it is true for n+1. Then, since it is true for 1, it is true for 2, and 3, and so on. 

Easy example: Prove the sum of the first n odd integers is n^2. 

Base case: n=1, 1^2=1, this is true.

Induction step:

If 1+3+5+...2n-1=n^2 for some n, let us add the next odd number, 2n+1, to both sides, so

1+3+5+...+2n-1+2n+1=n^2 + 2n +1 

but n^2+2n+1 is precisely (n+1)^2, so the statement is true for n+1.

As with the previous section, this is a technique I am very familiar with, but I just wanted to do the problems. I found the problems in this section generally not too difficult, because the way to start is generally clear. (Use induction). I find that working from this book, and making more concrete plans, gives me a much better work ethic, because I have to write a post for each section.

Here is an example from the text that is not quite as easy. 

Prove that for any positive integer n ≥ 2 there is a positive integer m that can be

written simultaneously as a sum of 2, 3, . . . , n squares of nonzero integers.

We will induct on n, as before:

base case: n=2

m=5 works, as

4=1^2 + 2^2

Induction step: so there is an integer m, such that for some n, 

m is expressible as the sum of 2,3..., n squares of integers. We would like to construct an integer m2 such that it is also the sum of n+1 squares of integers. Our first instinct is, naturally, to add a square to m. This gives us a number that is expressible as a sum of 3,4,...n+1 squares, which is almost what we want. So we would also like it to be expressible as a sum of 2 squares. So if

m2=m+c^2

m=a^2 + b^2,

so m2=a^2 + b^2 + c^2  We would like to pick c, such that we can "collapse" this into two squares.  However, this is easy, pick c so that a and c form the two legs of a right triangle. (There is an easy algorithm to generate all integer valued Pythagorean triples, I will talk about in separate post because there is a very nice way to find it)

So a^2 + c^2 = d^2, so m=d^2+b^2, so m is expressible as a sum of 2 squares, so we are done. 

(Note, if a=1, we can't make a triple, so we will use b instead, if b=1, then m=2, but 2 only works as a choice of m for n=2, and we can pick m=5 instead)