One more rule about Pythagorean triples

Yet again, let's consider Pythagorean triples, sets of three positive integers a, b and c such that a² + b² = c².  Here are several examples where all three numbers are less than 100.

3² + 4² = 5²
12² + 5² = 13²
15² + 8² = 17²
7² + 24² = 25²
9² + 40² = 41²
20² + 21² = 29²
48² + 55² = 73²

We know that we can generate Pythagorean triples using any two positive integers j and k with the formulas, where j > k with

a = j² - k²    b = 2jk and   c = j² + k²

This means there must be infinitely many different Pythagorean triples. If you aren't sure, consider k=1 and we get

a = j² - 1   b = 2j and  c = j² + 1

For any j > 1, we will get a unique Pythagorean triple.

Here's a pattern I noticed. Every triple on our list above has one number that is divisible by 5. Let us start with a speculation.

Speculation: Every Pythagorean triple has at least one number that is divisible by 5.

We could create a triple where all three numbers are divisible by 5 just by taking any Pythagorean triple and multiplying all the numbers by 5.

Example: Because  3² + 4² = 5², 15² + 20² = 25², The original numbers are 9 +16 = 25, and if we multiply all the numbers by 5, all the squares are multiplied by 25 and we get 225 + 400 = 625.

That explains why the modifier "at least" is used in the speculation.

Let's find facts that will help us prove the speculation.

Fact: The last digit of a square is determined by the last digit of the original number.

Think about multiplying two numbers that have two digits together, like 72 × 72. 

__72
_×72
_144
504 
5184

The ones place is just 2 × 2 and the 70 isn't involved. This would be true no matter how many digits in a number.

Fact: The last digit of a perfect square can only be 0, 1, 4, 9 or 6.

We can prove this by looking at the list of perfect squares of the numbers 0 through 9 (0, 1, 4, 16, 25, 36, 49, 64, 81) and using the first fact from above that the last digit of a number determines the last digit of the square.

Fact: The remainder of a perfect square when divided by 5 can only be 0, 1 or 4.

Because 10 = 2 × 5, the remainder upon division by 5 will look a lot like the last digit, except 6 becomes 1, and 9 becomes 4.

Fact: If you want to make a sum of two numbers from the set {0, 1, 4} to add up to 0, 1 or 4, there are only a finite number of patterns and not all of them work.

0 + 0 = 0 works
0 + 1 = 1 works
0 + 4 = 4 works
1 + 0 = 1 works
1 + 1 = 2 doesn't work
1 + 4 = 5 doesn't work, except when we divide 5 by 5 we get remainder 0, so it does work for us.
4 + 0 = 4 works
4 + 1 = 5  doesn't work, except when we divide 5 by 5 we get remainder 0, so it does work for us.
4 + 4 = 8 doesn't

Fact: Every pattern that works has a 0 or 5 in it.

Fact: A remainder of 0 when dividing by five means the number is divisible by 5.

Fact: Because 5 is prime, getting a perfect square that is divisible by 5 means the original number is divisible by 5.

This means our speculation about the Pythagorean triples is in fact a pattern that is always true. We could call it a "theorem", but I'm going to save that word for

Fact: Every Pythagorean triple has at least one number that is divisible by 5.

Here are two other facts that can be proved using similar methods, which the reader can try to prove if interested.

Fact: Every Pythagorean triple has at least one number that is divisible by 3.

Fact: Every Pythagorean triple has at least one number that is divisible by 2 and one number  divisible by 4.

We don't have any other primes for which this is true. That is proved simply by the triple 3, 4, 5. All the primes greater than 5 (7, 11, 13, 19, ...) do not divide any of these numbers evenly, so we have a single counter-example that works for an infinite number of cases, a situation a lazy mathematician is always happy to find.

Another rule about Pythagorean triples.

Last January, I wrote several posts about Pythagorean Triples, a set of three whole numbers a, b and c that follows the rule of the Pythagorean Theorem a² + b² = c². Here are some examples.

3² +4² = 5²
8² + 15² = 17²
24² + 7² = 25²

If we think about these numbers as sides of a triangle, the area will be ½ab. In the cases from above, the areas as 6, 60 and 84, respectively.

There is a way to generate all such whole number triples, using two positive integers j and k, with j>k.

a = j² - k²
b = 2jk
c = j² + k²

Our first rule is that we should stipulate that j does not equal k, because in the that case a = 0. Re-writing a and b in the area formula into multiples of j and k, we get this.

Area = ½ab = ½(j² - k²)2jk = (j² - k²)jk

Since j and k are whole numbers, the area must be a whole number. But more than that the number must be divisible by 6. The proof is split into two parts, first that the area is divisible by 2 and secondly that the area is divisible by 3.

Proof of the area is divisible by 2. If j or k is even, then (j² - k²)jk is even, since if you have a product of whole numbers and one is even, the product is even. The only other option is that both j and k is odd, and if that is the case then j² - k² = odd - odd = even.

Proof of the area is divisible by 3. If j or k is a multiple of 3, then (j² - k²)jk is a multiple of 3. The only other option is that neither j and k is a mulitple of 3. For any number n that isn't a multiple of 3,  n² will be of the form 3p + 1, which is to say one more than some multiple of 3. If that is the case then j² - k² = (3p + 1) - (3q + 1) = 3(p- q), which is a multiple of 3 as well.

Dr. Kenneth Appel and the Four Color Map Theorem: Part 2

When mathematicians look at the four color map problem, they often turn the regions into vertices or nodes - here represented by ovals - and draw a line between any two nodes whose regions share a border. This object is called a graph, and because none of the lines connecting nodes crosses any other, the specific type of graph is called planar.

Dr. Kenneth Appel proved that all such planar graphs can be painted with four or less colors such that no two nodes that have a line connecting them directly are the same color. If you think about any graph, you could always add a new node an a few lines from that node to some of the other nodes on the existing graph. The implication of this is that there are infinitely many graphs.

Here's the tricky part of Dr. Appel's proof and I will not try to present an explanation for it.  There are ways to make one graph equivalent to another, which means that if one graph can be four-colored, the equivalent graph can be four-colored as well. Even though there are infinitely many graphs, Dr. Appel's method proved there are exactly 1,936 different equivalence classes.

It's not uncommon for mathematical proofs to have to several cases that have to be taken separately, but 1,936 is a lot of cases.  Instead of doing each one by hand, Appel decided to write a computer program that looked at every case. When it was finished and it had looked at all the data, it had proved each of the cases could be color with no more than four colors and the proof was complete.

There were many mathematicians who were not satisfied with the new method, but there were many who saw this as a way to use computers to forward the field of mathematical inquiry. While the controversy is not yet over, Appel's proof is accepted and the use of computers in math research is much more common now than it was in the 1970s.

Best wishes to the family and friends of Dr. Kenneth Appel, from a fan.

Dr. Kenneth Appel and the Four Color Map Theorem: Part 1

Dr. Kenneth I. Appel died earlier this month at the age of 80. He is best known in mathematics four proving the Four Color Theorem, which states that any map of regions drawn on a flat piece of paper can be colored with no more than four colors in such a way that no two neighboring regions are the same color.

The proof was controversial in its day - the 1970s - because it used a computer to complete a vital but time consuming step.

Here is a map of the Western United States. Let me show a way to color it using four colors. It is not unique and the method I use causes a problem at the end, but by switching things around that problem can be solved.

An important idea in map coloring is that two regions are adjacent if they have a common edge, not if they meet at a common corner. In this example we have the four states that meet at a corner, In the same way a checkerboard can use two colors without people being confused, we can have Arizona and Colorado share a color, here signified by the number 1, and New Mexico and Utah share a different color, signified by the number 2.

Having done this, we now have states that border a 1 state and a 2 state, so I give all these states - Nevada, Wyoming and Oklahoma - the number 3.

Having done things in this method, I will now be forced to use a fourth color when mapping Kansas and Nebraska, and likewise there will be a forcing issue once, California, Oregon and Idaho are colored in. I also colored in Texas with a 1 since it was bordered by a 2 and 3.

I can easily finished the rest of the map, but this pattern has a problem. Imagine that some single region surrounds all these states. Because states on the outside edges have all four colors, this huge imagined state would have to be a fifth color, which would say four colors do not suffice. If I had started the problem knowing about that constraint, I could have still solved the new problem with four colors. The easiest way to do this changing as few states as possible is to switch the 3 and 4 in Wyoming and Nebraska, switch the 3 and 4 in Nevada and Oregon and change Washington to a 2. Then all the states on the outside have the numbers (colors) 1, 2 and 3 and the surrounding region can be given the color 4.

Tomorrow, I'll give a sketch of the proof, glossing over some difficult math and discussing the controversy of using computers in proofs.

I present this picture as tribute of the moment. Appel was at the University of Illinois when he published and the local post office commemorated his achievement with this postmark stating FOUR COLORS SUFFICE. It became a collector's item for mathematicians, like this postcard sent from the Urbana post office to Ulm, Germany while the postmark was being used.
 

Two picture proofs of the Pythagorean Theorem.

Here are two squares that are the same size. In the left square, we will label the blue square a² and the red square b².  The two white rectangles both have area ab. Together, they show the famous "middle term" representation of

(a + b)² = a² + 2ab + b²

The square on the right has four white right triangles that are the equivalent of the two white rectangles sliced diagonally, where the diagonal is the hypotenuse, which we usually label c. The yellow square with the gap in it has area c².  Since the squares are the same size we get

c² + 4(½ab) = a² + 2ab + b²  Next step: get rid of the parentheses

c² + 2ab = a² + 2ab + b²  Next step: subtract 2ab from both sides

c²  = a² + b²  and we are done.

Second proof just using the yellow square and the gap inside.

The gap in the middle of the yellow square is (a - b)² = a² - 2ab + b². The four yellow triangles are 2ab, exactly the same as the four white triangles. That means this picture tells us

c² = a² - 2ab + b² + 2ab

So we combine like terms to get
 
c²  = a² + b²  and once again, Q.E.D., the Latin abbreviation for "that which has been demonstrated".

Tomorrow: number theory and Pythagorean Theorem.

The sum of the n-th row of Pascal's Triangle is 2 to the n-th power

Yesterday, we proved the statement that is the title of this post. Why prove it again?

Proof in mathematics is vitally important and multiple proofs of the same fact (or theorem) can show different ways things are connected to each other.

The style of proof we see today is called induction. Here is the basic idea.

1. Make a statement about an infinite number of things that you can put in order.
2. Prove it for the first thing.
3. Prove that if it is true for any given thing on the list, it must also be true for the next thing on the list.

The infinite things we are putting in order are the sums of the rows of Pascal's Triangle.

1=1
2=1+1
4=1+2+1
8=1+3+3+1
...

The first thing on the list is the sum of 1 in row 0. 1 = 2º, so that means we have done steps 1 and 2 of induction.

Now I'm going to cheat a little to make things clear. I am going to use the third row of Pascal's Triangle for my next step. I shouldn't use a specific row because induction has to be about any given row. I'm going to cheat here to convince the reader that what happens to go from the third row to the fourth row happens going from any row to the next.  I'm going to use four different colors on the four different numbers.

1 3 3 1 

next row created by adding numbers from the current row. (0 are in black.)

0+1 1+3 3+3 3+1 1+0

Notice that every color of number shows up exactly twice, two purple 1s, two red 3s, two green 3s and two blue 1s. This means that the sum of this row must be exactly twice the sum of the row we were looking at.

Proving this is true between rows three and four is not enough. You need to convince yourself the pattern of doubling is true between any two consecutive rows. The reason that it's true is that every number in a row is used exactly twice in two different sums to create the entries of the next row.

Tomorrow, we continue to look at patterns in Pascal's Triangle.  We have seen the Christmas Stocking, now we will discover the hockey stick.
 
 

The sum of the n-th row of Pascal's Triangle is always 2 to the power of n.

Yesterday, we discussed the Binomial Theorem, the standard way to expand a binomial, here expressed as (x + y), raised to any positive integer power n.


We also have a simple pattern easily visible in the first few rows of Pascal's Triangle.

1 = 1
2 = 1+1
4 = 1+2+1
8 = 1+3+3+1
16= 1+4+6+4+1
...

From what we can see, the sum of the n-th row is 2 raised to the power of n. In math, we can't just say we see a pattern for a few rows and assume it is always true, we need to prove it is true. Here is the proof.
  

Step 1 is no more difficult than 2 = 1+1.  Pretty easy.

Step 2 is to take the Binomial Theorem and replace the general binomial (x + y) with the specific binomial (1+1). So we get all the entries of row n multiplied by powers of 1 then added up.

Any integer power of 1 is 1, so we can erase those powers because they are superfluous.

Now we just have the sum across the row. Since the equations are of the form

a = b, then b = c, then c = d, we can also say a = d.

This is not the only way to prove this. Another proof of this basic property of Pascal's Triangle tomorrow.

An informal proof of the Christmas Stocking Theorem

Let's put a few rows of Pascal's triangle up yet again and choose one of the entries "at random", providing it isn't in the leftmost column.

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
1  6 15 20 15  6  1
1  7 21 35 35 21  7  1
1  8 28 56 70 56 28  8  1

The first rule we have learned about entries in that any entry is the sum of the entry just above it and the entry above it and to the left, in this case, 35+21 = 56.


1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
1  6 15 20 15  6  1
1  7 21 35 35 21  7  1
1  8 28 56 70 56 28  8  1

I'm going to use the same rule on the 21, changing it to 15+6, the entries above it.

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
1  6 15 20 15  6  1
1  7 21 35 35 21  7  1
1  8 28 56 70 56 28  8  1

Now the 6,  changing it to 5+1, the entries above it.

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
1  6 15 20 15  6  1
1  7 21 35 35 21  7  1
1  8 28 56 70 56 28  8  1

Now the 1 in row 5 is exchanged for the 1 in row 4, actually 1 = 1+0, but the zero is invisible.

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
1  6 15 20 15  6  1
1  7 21 35 35 21  7  1
1  8 28 56 70 56 28  8  1

Now I un-bold the 1 in row 5 and we have our standard Christmas Stocking, the sum of the leg in bold red being equal to the toe in bold black.


1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
1  6 15 20 15  6  1
1  7 21 35 35 21  7  1
1  8 28 56 70 56 28  8  1

Here is how I could say the theorem in everyday language.

Pick any column in Pascal's Triangle.  Starting at the top of the column, select as many entries as you want and add them up. The sum will be equal to the entry that is one row down and one column to the right of the position where you list of entries ended.

Here is how I would write this in summation notation.  The letter k stands for the column, the letter n stands for where we stop counting and the letter j is the summation variable, which goes from k to n.

Here is how I would say this summation out loud if I were explaining it in class.

The sum as j goes from k to n of "j choose k" is "n+1 choose k+1".

The parentheses with two numbers on top of each other is the standard way to write the numbers of Pascal's Triangle, known collectively as the binomial coefficients. The editor that Blogger uses doesn't have an elegant way to put up a summation symbol or stacking numbers inside a parentheses, so I will write "8 choose 5" = 56 when I mention an entry or "j choose k" when discussing a general entry.

Tomorrow: Why the entries are called binomial coefficients.