You can count on my proof?
Combinatorial Proofs Research Project
Author: Mel Koppens (mkoppens@email.arizona.com)
Advisors: Dr. Pallavi Jayawant & Dr. John Leonard
Date: 012604
Abstract:
Combinatorial proofs provide a valuable alternative for algebraic methods. They are generally shorter, more elegant and above all far easier to understand especially by people not considered experts in the area of mathematics. This paper is based on a book called “Proofs that really count” by Benjamin & Quinn. The bulk of this writing deals with solving identities using a combinatorial approach. Most of the identities discussed stem from the book mentioned but there are a few identities, which are original.
I.
Introduction
Mathematical identities like the Fibonacci identities are widely studied in the mathematical community. I approached the subject from a combinatorial point of view and gained new insights into the inner working of these sorts of identities. As a starting point and rough guideline for my research, I used the book “Proofs that really count” by Benjamin & Quinn.
A lot of the terminology used in this paper
is in accordance with the abovementioned book so please refer to it for a
detailed discussion of the definitions and conventions that are used in this
writing.
Most of this paper was written and edited
using Word, and converted into HTML by word.
This document is therefore best viewed as a word document. Be aware that because of some anomalies
caused by internetbrowsers, some of the figures might not be scaled right and
the numbering of the cells might be off.
In particular figure 2.m01 seems to be affected. I apologize for this inconvenience.
I would like to acknowledge Dr John L.
Leonard and Dr Pallavi. Jayawant for their help and support. They were an appreciated audience for my
presentations and provided me with the necessary feedback.
II.
Selected
identities from Chapter 1
Identity 12: For n ³ 1, f1 + f3 + … + f2n1 = f2n – 1.
Question: How many tilings of a 2nboard use at least 1 square?
Answer 1: There are f2n tilings of a 2n board. Excluding the “all domino” tiling gives f2n – 1 tilings with at least one square.
Answer 2: Condition on the location of the last square. There are f2k1 tilings where the last square covers cell k. This is because cells 1 thru 2k1 can be tiled in f2k1 ways, cell 2k is covered by a square, and dominos must cover cells 2k+1 thru 2n. Hence the total number of tilings with at least one square is f1 + f3 + … + f2n1.





. . . 





f2n1
1 2 3 4 5 2n4 2n3 2n2 2n1 2n





. . . 




f2n3
1 2
3 4 5 2n4 2n3 2n2 2n1 2n





. . . 



f2n5
1 2
3 4 5 2n4 2n3 2n2 2n1 2n
. .
. .
. .





. . . 



f3
1 2 3 4 5 2n4 2n3 2n2
2n1 2n




. . . 



f1
1 2 3 4 5 2n4 2n3 2n2 2n1 2n
Figure 1.12: To
see that f1 + f3 + … + f2n1 = f2n – 1, tile an
2nboard with squares and dominoes and condition on the location of the last
square.
Identity 13: For n ³ 0, fn^{2} + fn+1^{2} = f2n+2.
Question: How many tilings of a (2n+2)board exist?
Answer 1: By definition, there are f2n+2 such tilings.
Answer 2: Condition on the breakability at cell n+1. If the (2n+2)board is breakable at cell n+1, then the (2n+2)board can be divided into two (n+1)boards. These two boards can be tiled in fn+1^{2} ways. If the (2n+2)board is not breakable at cell n+1 a domino must cover cells n+1 and n+2. Now cells 1 thru n can be tiled in fn ways and cells n+3 thru 2n+2 can be tiled in fn ways, yielding fn^{2} tilings. All together there are fn^{2} + fn+1^{2} ways to tile an (2n+2)board.
Breakable at cell n+1:


. . . 




. . . 


fn+1^{2}
1 2 n n+1 n+2
n+3 2n+1 2n+2
Not breakable at cell n+1:


. . . 



. . . 


fn^{2}
1
2
n n+1 n+2 n+3 2n+1 2n+2
Figure 1.13: To
see that fn^{2}
+ fn+1^{2}
= f2n+2, condition
on the breakability of a 2n+2 tiling at cell n+1.
Identity 25: For n ³ 1, 2f1 + 2f4 + 2f7 + … + 2f3n2 = f3n – 1.
Question: Define a 21triplet as a 3cell covering in which a domino is immediately followed by a square. How many tilings are there on a 3nboard that is not entirely made up by 21triplets?
Answer 1: There are f3n – 1 such tilings, since there is exactly one 3n tiling solely made up by 21triplets.
Answer 2: We count how many tilings end in exactly p consecutive triplets where n > p ³ 0. In such a tiling, cells 3(np)+1 thru 3n are covered by p 21triplets and cells 3(np)2 thru 3(np) do not form a (21)triplet. This implies on of two things. Either cells 3(np)1 and 3(np) are covered by a domino or these two cells are covered by two squares. In each case the remaining cells 1 thru 3(np)2 can be stacked in f3(np)2 ways. So for each p there are a total of 2f3(np)2 tilings. Letting p range from n1 to 0 amounts to a total of 2f1 + 2f4 + 2f7 + … + 2f3n2 tilings.
Ending in no triplets:






. . . 





f3n2
1 2 3 4 5 6 3n5 3n4 3n3 3n2 3n1 3n
or






. . . 






f3n2
1 2 3 4 5 6 3n5 3n4 3n3 3n2 3n1 3n
Ending in exactly1 triplets:






. . . 




f3n5
1
2 3 4 5 6
3n5 3n4 3n3 3n2 3n1 3n
or






. . . 





f3n5
1
2 3 4 5 6
3n5 3n4 3n3 3n2 3n1 3n
. .
. .
. .
Ending in exactly n1 triplets:




. . . 




f1
1 2 3
4 5 6 3n5 3n4
3n3 3n2 3n1
3n
or





. . . 




f1
1 2 3
4 5 6
3n5 3n4 3n3 3n2 3n1 3n
Figure 1.25: To
see that 2f1 +
2f4 + 2f7 + … + 2f3n2 = f3n – 1, count how many
tilings end in exactly p 21triplets.
Interpretation 1: For n ³ 1, fn+1 counts binary ntuples with no consecutive 0s.
Reason: Consider the mapping M: {tilings length n+1}→ {ntuplets with no consecutive 0s} and its inverse mapping Minv defined as follows:
Given an (n+1)tiling, M replaces every domino by 01 and every square by 1. M then drops the last ‘1’ creating an ntuplet with no consecutive zeros.
Given an n tuplet with no consecutive zeros add a 1 to the right. Reading from left to right Minv replaces each 01 by a domino and each 1 by a square, creating an (n+1)tiling.






→ 0 1 1 0 1 1 1 0
M






← 1 0 1 0 1 1 0 1
Minv
It is obvious that this is a onetoone mapping between the two sets.
III.
Selected
Identities from Chapter 2
Identity 62: For n ³ 0, G1 + Σ(1 to n) G2k = G2n+1.
Question: How many phased tilings of an (2n+1)board exist?
Answer 2: Condition on the location of the last square. Since there are an odd number of cells, there must be at least one square in the tiling and this square occupies an odd numbered cell say 2k+1. There are G2k such tilings. There is one special case in which there is exactly one square and it is the first (phased) square. In this case there are G1 tilings. Hence the total number of tilings is G1 + Σ(1 to n) G2k.
Identity m01: For n ³ 1 and n > k > 0^{(*)}, Gn^{2} = Gn+kGnk + (1)^{k+n+1}fk1(Gn+1G0 – GnG1).
Set 2: The set of tiling pairs of a phased (n+k)board and a phased (nk)board, where the initial conditions of both the boards are determined by G0 and G1.
Correspondence: To understand the identity it is best to refer to the picture below as you read the text. Place one of the nboards on top of the other nboard, such that the bottom one is k cells offset to the right as in figure 2.m01. If we now tail swap the faulty tilings of set 1, we create all the faulty tilings of set 2. What we need to do is count the number of fault free tilings in each set, which depend on the parity of nk. Let’s assume that nk is odd.
Set 1 fault free sets: (p indicates a phased tile)
p 
. . . 




. . . 

1 2 k k+1 n1 n
p 

. . . 


. . . 

k+1 n1 n n+1 n+2 n+k
Set 2 fault free sets:
p 
. . . 



. . . 


. . . 

1 2 k
k+1 n1 n
n+1 n+2 n+k
p 


. . . 

k+1 n1 n
Figure 2.m01: When nk is odd, there are Gk+1G0fk1 fault free tilings in set 1 GkG1fk1 fault free tilings in set 2. All other tilings from set 1 and set two form a onetoone correspondence using tailswapping.
The fault free tilings in set 1 consist of a phased (k+1)tiling followed by (nk1)/2 dominoes covering cells k+2 thru n in the top board and the bottom board has (nk+1)/2 dominoes covering cells k+1 through n+1 (with the first domino being a phased domino) followed by an unphased (k1)tiling. This leads to Gk+1G0fk1 fault free tilings in set 1. In a similar fashion be we find GkG1fk1 fault free tilings in set 2. As a result when nk is odd, the difference in size between set 1 and set 2 is equal to the difference in size between the fault free tilings of set 1 and set 2. Thus
Gn^{2} – Gn+kGnk = Gk+1G0fk1 – GkG1fk1.
After rearranging the above equation, we get
Gn^{2} = Gn+kGnk + fk1(Gk+1G0 – GkG1).
Using a similar procedure we can show that
Gn^{2} = Gn+kGnk – fk1(Gk+1G0 – GkG1)
when nk is even. This proves the identity. (Note (*): The identity holds even when n ³ k ³ 0 )
Identity m02: For k ³ 0 and, Gk+1G0 – GkG1 = fk1(G2G0 – G1^{2}).
Proof: This is the only identity I was not able to prove with a “pure” combinatorial argument. When k = 0 or k =1 the identity is trivial. In case k > 1 it is clear that Gk+1 = G1fk + G0fk1 since a phased (k+1)tiling either starts with a phased square or a phased domino. Similarly we find Gk = G1fk1 + G0fk2. When both expressions are substituted in the left hand side of the identity, it is a rather easy exercise to show that the identity indeed holds. Just keep in mind that fk2 + fk1 = fk and G0 + G1 = G2. With the help of this identity we can now find a more elegant form for identity m01.
Identity m03: For n ³ 1 and n ³ k ³ 0, Gn^{2} = Gn+kGnk + (1)^{k+n+1}fk1^{2}(G2G0 – G1^{2}).
Proof: Simply combine the results of identities m01 and m02.
IV.
Discussion
There are quit a few other identities that I
managed to proof. I choose not to write
them in this paper because they were either too similar to other identities or
they simply did not provide any interesting results. Other identities, like m03, can be used to proof a whole series
of other identities, simply by making substitution or shifting variables.
The whole subject of combinatorial proofs is very inviting. It takes quit a bit of effort to get your
mind thinking in the right fashion but the rewards are plentiful. There is an enormous body of work out there
in this field, some already explored, but most of it is waiting for a clever
mind to unwrap its mystery.