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:  01-26-04

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 above-mentioned 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 internet-browsers, 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 + … + f2n-1 = f2n – 1.

Question:  How many tilings of a 2n-board 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 f2k-1 tilings where the last square covers cell k.  This is because cells 1 thru 2k-1 can be tiled in f2k-1 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 + … + f2n-1.

 .  .  .

f2n-1

1        2       3        4       5                                                              2n-4  2n-3  2n-2  2n-1   2n

 .  .  .

f2n-3

1        2       3        4        5                                                             2n-4  2n-3  2n-2  2n-1   2n

 .  .  .

f2n-5

1        2       3        4        5                                                             2n-4  2n-3  2n-2  2n-1   2n

.                                                                                   .

.                                                                                   .

.                                                                                   .

 .  .  .

f3

1       2        3       4        5                                                              2n-4   2n-3 2n-2   2n-1   2n

 .  .  .

f1

1        2        3      4         5                                                             2n-4   2n-3 2n-2   2n-1  2n

Figure 1.12:    To see that f1 + f3 + … + f2n-1 = f2n – 1, tile an 2n-board with squares and dominoes and condition on the location of the last square.

Identity 13:     For n ³ 0, fn2 + fn+12 = 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+12 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 fn2 tilings.  All together there are fn2 + fn+12 ways to tile an (2n+2)-board.

Breakable at cell n+1:

 .  .  . .  .  .

fn+12

1       2                                        n      n+1   n+2   n+3                                 2n+1 2n+2

Not breakable at cell n+1:

 .  .  . .  .  .

fn2

1       2                                        n    n+1     n+2   n+3                                 2n+1 2n+2

Figure 1.13:    To see that fn2 + fn+12 = f2n+2, condition on the breakability of a 2n+2 tiling at cell n+1.

Identity 25:     For n ³ 1, 2f1 + 2f4 + 2f7 + … + 2f3n-2 = f3n – 1.

Question:  Define a 2-1-triplet as a 3-cell covering in which a domino is immediately followed by a square.  How many tilings are there on a 3n-board that is not entirely made up by 2-1-triplets?

Answer 1: There are f3n – 1 such tilings, since there is exactly one 3n tiling solely made up by 2-1-triplets.

Answer 2: We count how many tilings end in exactly p consecutive triplets where n > p ³ 0.  In such a tiling, cells 3(n-p)+1 thru 3n are covered by p 2-1-triplets and cells 3(n-p)-2 thru 3(n-p) do not form a (2-1)-triplet.  This implies on of two things.  Either cells  3(n-p)-1 and 3(n-p) are covered by a domino or these two cells are covered by two squares.  In each case the remaining cells 1 thru 3(n-p)-2 can be stacked in f3(n-p)-2 ways. So for each p there are a total of 2f3(n-p)-2 tilings.  Letting p range from n-1 to 0 amounts to a total of 2f1 + 2f4 + 2f7 + … + 2f3n-2 tilings.

Ending in no triplets:

 .  .  .

f3n-2

1        2       3       4         5       6                                      3n-5 3n-4   3n-3  3n-2  3n-1   3n

or

 .  .  .

f3n-2

1       2        3       4        5         6                                     3n-5 3n-4   3n-3 3n-2   3n-1   3n

Ending in exactly1 triplets:

 .  .  .

f3n-5

1       2        3        4        5        6                                     3n-5  3n-4  3n-3  3n-2  3n-1   3n

or

 .  .  .

f3n-5

1       2        3       4        5        6                                      3n-5  3n-4  3n-3  3n-2  3n-1   3n

.                                                                                   .

.                                                                                   .

.                                                                                   .

Ending in exactly n-1 triplets:

 .  .  .

f1

1       2         3      4         5       6                                       3n-5 3n-4  3n-3  3n-2  3n-1   3n

or

 .  .  .

f1

1       2       3        4       5        6                                       3n-5 3n-4  3n-3  3n-2  3n-1   3n

Figure 1.25:    To see that 2f1 + 2f4 + 2f7 + … + 2f3n-2 = f3n – 1, count how many tilings end in exactly p 2-1-triplets.

Interpretation 1:         For n ³ 1, fn+1 counts binary n-tuples with no consecutive 0s.

Reason:          Consider the mapping M: {tilings length n+1}→ {n-tuplets 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 n-tuplet 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 one-to-one 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 1:By definition there are G2n+1 such tilings.

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(*), Gn2 = Gn+kGn-k + (-1)k+n+1fk-1(Gn+1G0 – GnG1).

# Set 1:The set of tiling pairs of two phased n-boards, where the initial conditions of both the boards are determined by G0 and G1.

Set 2:        The set of tiling pairs of a phased (n+k)-board and a phased (n-k)-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 n-boards on top of the other n-board, 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 n-k.  Let’s assume that n-k is odd.

Set 1 fault free sets: (p indicates a phased tile)

 p .  .  . .  .  .

1       2                    k      k+1                                                                n-1    n

 p .  .  . .  .  .

k+1                                                              n-1     n      n+1  n+2                      n+k

Set 2 fault free sets:

 p .  .  . .  .  . .  .  .

1       2                      k     k+1                                                               n-1    n       n+1  n+2                      n+k

 p .  .  .

k+1                                                               n-1    n

Figure 2.m01: When n-k is odd, there are Gk+1G0fk-1 fault free tilings in set 1 GkG1fk-1 fault free tilings in set 2.  All other tilings from set 1 and set two form a one-to-one correspondence using tail-swapping.

The fault free tilings in set 1 consist of a phased (k+1)-tiling followed by (n-k-1)/2 dominoes covering cells k+2 thru n in the top board and the bottom board has (n-k+1)/2 dominoes covering cells k+1 through n+1 (with the first domino being a phased domino) followed by an unphased (k-1)-tiling.  This leads to Gk+1G0fk-1 fault free tilings in set 1.  In a similar fashion be we find GkG1fk-1 fault free tilings in set 2.  As a result when n-k 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

Gn2 – Gn+kGn-k = Gk+1G0fk-1 – GkG1fk-1.

After rearranging the above equation, we get

Gn2 = Gn+kGn-k + fk-1(Gk+1G0 – GkG1).

Using a similar procedure we can show that

Gn2 = Gn+kGn-k – fk-1(Gk+1G0 – GkG1)

when n-k is even.  This proves the identity.  (Note (*):  The identity holds even when n ³ k ³ 0 )

Identity m02:  For k ³ 0 and, Gk+1G0 – GkG1 = fk-1(G2G0 – G12).

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 + G0fk-1 since a phased (k+1)-tiling either starts with a phased square or a phased domino.  Similarly we find Gk = G1fk-1 + G0fk-2.  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 fk-2 + fk-1 = 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, Gn2 = Gn+kGn-k + (-1)k+n+1fk-12(G2G0 – G12).

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.