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 G