Last week, in Fundamental Understanding of Mathematics LXIV we took a look at a kind of proof called a "proof by induction" which is a two part proof.
First, we prove that some base fact is true.
Next, we prove that we can produce the next fact in a series if we assume the prior fact is true.
We will work out another example this week.
We will begin by taking a look at odd numbers. We all know what they are: 1, 3, 5, 7, 9, and so on.
They are the numbers that don't pair up evenly. If we divide an odd number by 2, we will have one left over.
Odd or even?
Pair them up and it is easy to tell...
This is an odd number of squares.
Mathematically, we can make an odd number by multiplying some integer by two, and either adding or subtracting one. Multiplying by two gives us paired up numbers, and adding or subtracting one makes the number odd.
So the definition of an odd number could be
Odd number = 2N +1 or Odd number = 2N -1
If we restrict N to the counting numbers (1, 2, 3, ...) so we have a count of the number of Odd numbers, then we will have to use Odd number = 2N – 1, otherwise, our first odd number would be three instead of one. Computer programmers, who start counting from zero, can use 2N+1, but for the rest of us mortals, saying the zeroth odd number is one just doesn't sound right.
Here are the first four odd numbers, 1, 3, 5 and 7
We will add them up, and see what we get. N is the number of Odd numbers we add up.
N= 1: 1 = 1
N= 2: 1 + 3 = 4
N= 3: 1 + 3 + 5 = 9
N= 4: 1 + 3 + 5 + 7 = 16
There seems to be a pattern. Let's take a look at it using diagrams
N=1:
N=2:
N=3:
N=4
The pattern is the sum of all the odd numbers (starting at one) is N squared.
The peculiar looking symbol on the left of the equal sign is an abbreviation for summing up a list of numbers. The "1" underneath the symbol (Capital Sigma, in Greek, by the way) gives the starting number, and the "N" on top gives the ending number. After the sign you find a pattern or expression for figuring out what to add up, in this case, odd numbers.
So, what we are really saying is that
Can we prove it?
The first step in the proof is already done. We can look at the example and see that the formula works for N=1, N=2, N=3, N=4.
The second step is to show that we can go from some arbitrary N to N+1. If we can do this, we have shown that we can start on any of our first four steps, and go as high as we please. To infinity, as Buzz Lightyear says, and beyond.
We begin by rewriting Nth Odd Number using our earlier definition for Odd Numbers:
Nth Odd number = 2N – 1
Now, we assume that the formula is true, so we can say
and we want to find out whether adding the next odd number, 2(N+1)-1 means the sum is the square of N+1
We can replace the beginning series,
So
We will use the distributive property on the left hand side to remove the parenthesis around N+1, and rewrite the right hand side without the exponent.
Next, we can do the bit of arithmetic on the left side, 2-1, and use the distributive property to remove one set of parentheses on the right side.
Using the distributive property again on the right side gives
And we can add up the N+N to get 2N on the right side, which results in
Once we see the stuff on the left side is the same as the stuff on the right side, we can say the equation is true. Which means the equation we started with is true, too.
So this shows we can get from any step to the next higher step in our series of sums of odd numbers. Since we know that the formula works for the first four steps, we have proved it.
Have fun in the comments.