Tiling a (n x 1) Checkerboard

[Rebecca421]

I am trying to come up with an identity using a combinatorial proof by considering a (n x 1) checkerboard, and examining what happens if you focus on the split between the first and second tiles (split A) and the split between the (n-1)th and (n)th tiles (split B). You can cover a tile with either a square or a domino (if you use a domino it covers 2 tiles).

It is given that there are four cases, 2 of which are identical, and that one of the cases is a domino on both A and B.


I'm not sure why there are only four cases or what they should be.

 

[Harry_the_cat]

I am trying to come up with an identity using a combinatorial proof by considering a (n x 1) checkerboard, and examining what happens if you focus on the split between the first and second tiles (split A) and the split between the (n-1)th and (n)th tiles (split B). You can cover a tile with either a square or a domino (if you use a domino it covers 2 tiles).

It is given that there are four cases, 2 of which are identical, and that one of the cases is a domino on both A and B.


I'm not sure why there are only four cases or what they should be.

Are the first 4 rows here what you mean? (Black is a domino, grey is a single tile - domino "covers" the split, a single tile doesn't.)

So the "splits" can be:
covered and covered
uncovered and uncovered
covered and uncovered
uncovered and covered

But then there could be the arrangement as shown in the fifth row, for example. Is that another way you need to consider or is that considered the same as being "uncovered"?

 

[Rebecca421]

Yes, a domino covers 2 spaces so it will cover the split and a square only covers one so it won't.

I figured out what the four cases are. You are supposed to condition the tiling on the first and last tiles, so the four cases would be what you said:

1. Domino, Domino
2. Square, Square
3-4. Square, Domino

My question is, how do you know from the prompt that you are conditioning on the first and last tiles and not the first two tiles and the last two tiles? If there wasn't that condition, it would include the 5th row in your picture and the identity would be more complicated.

The identity that I got was right so I'm pretty sure these are the four cases:
f_n = f_n-4 + f_n-2 + 2f_n-3 where f_n is the nth number in the Fibonacci sequence.

 

[Dr.Peterson]

I am trying to come up with an identity using a combinatorial proof by considering a (n x 1) checkerboard, and examining what happens if you focus on the split between the first and second tiles (split A) and the split between the (n-1)th and (n)th tiles (split B). You can cover a tile with either a square or a domino (if you use a domino it covers 2 tiles).

It is given that there are four cases, 2 of which are identical, and that one of the cases is a domino on both A and B.


I'm not sure why there are only four cases or what they should be.

I think it will help if you state the entire problem, as given to you.

It sounds like you are trying to count the number of ways to cover an n x 1 strip with any combination of 1- and 2-unit-long tiles.

What is the specific identity you want to prove, and what were you told, specifically, about cases? Is that a hint, or an actual "given"?

 

[Rebecca421]

I think it will help if you state the entire problem, as given to you.

It sounds like you are trying to count the number of ways to cover an n x 1 strip with any combination of 1- and 2-unit-long tiles.

What is the specific identity you want to prove, and what were you told, specifically, about cases? Is that a hint, or an actual "given"?

Here is the actual problem:



The idea of tiling like this helps you find the nth Fibonacci number.
I'm trying to come up with an identity based on the question, there is no identity given. To do this I used a combinatorial proof:

​

Question: How many ways can I tile an n x 1 checkerboard with squares and dominoes?
Left Hand Side: f_n by definition
Right Hand Side: There are four possibilities if you condition on what happens before A and after B:​

1. 
   [*=2]Dominoes on both ends (covers 4 spaces) --> f_n-4
   [*=2]Squares on both ends (covers 2 spaces) --> f_n-2
   [*=2]Domino over A, Square after B (covers 3 spaces) --> f_n-3
   [*=2]Square before A, Domino over B (covers 3 spaces) --> f_n-3

Because this is a combinatorial proof, the Left Hand Side is equal to the Right Hand Side and the cases are added together. So, you arrive at the identity:
f_n = f_n-4 + f_n-2 + 2f_n-3
​

f_n is a representation of the nth Fibonacci number, so for example f₁₀ = 89 = 13 + 34 + 2(21)

 

[Rebecca421]

Here is the original question:


The point of the question is to use this method of "tiling" to come up with an identity for finding the nth Fibonacci number by way of a combinatorial proof.
The number of ways to tile an n x 1 board is f_n. f_n also means the nth Fibonacci number.

The proof goes as follows:
Question: How many ways can you tile a n x 1 checkerboard?

​

Left Hand Side: f_n, by definition
Right Hand Side: I am going to condition on what happens before A and after B​

Case 1: Dominoes over both A and B (covers 4 spaces on the board) --> f_n-4
Case 2: Squares on both ends (covers 2 spaces) --> f_n-2
Case 3: Square before A, Domino over B (covers 3 spaces) --> f_n-3
Case 4: Domino over A, Square after B (covers 3 spaces) --> f_n-3​

Because it's a combinatorial proof the right hand side equals the left hand side. So the identity that you get is:
f_n = f_n-4 + f_n-2 + 2f_n-3

For example, f₁₀ = 89 = 13 + 34 + 2(21)


I understand the proof, the part I don't understand is why what happens on the right of A and on the left of B does not matter. If it did, there would be more cases and the identity would be different, but it would be equally valid. So how do you know to condition on what happens before A and after B?

 

[Dr.Peterson]

Here is the original question:
View attachment 10689

The point of the question is to use this method of "tiling" to come up with an identity for finding the nth Fibonacci number by way of a combinatorial proof.
The number of ways to tile an n x 1 board is f_n. f_n also means the nth Fibonacci number.

The proof goes as follows:
Question: How many ways can you tile a n x 1 checkerboard?

Left Hand Side: f_n, by definition
Right Hand Side: I am going to condition on what happens before A and after B​

Case 1: Dominoes over both A and B (covers 4 spaces on the board) --> f_n-4
Case 2: Squares on both ends (covers 2 spaces) --> f_n-2
Case 3: Square before A, Domino over B (covers 3 spaces) --> f_n-3
Case 4: Domino over A, Square after B (covers 3 spaces) --> f_n-3​

Because it's a combinatorial proof the right hand side equals the left hand side. So the identity that you get is:
f_n = f_n-4 + f_n-2 + 2f_n-3

For example, f₁₀ = 89 = 13 + 34 + 2(21)

I understand the proof, the part I don't understand is why what happens on the right of A and on the left of B does not matter. If it did, there would be more cases and the identity would be different, but it would be equally valid. So how do you know to condition on what happens before A and after B?

It really helps when you show the problem as given, along with your work! (We ask you to do that, here.) We've also now learned something about the context, which is also important; you are apparently learning about the Fibonacci sequence and such, which I would have guessed, but wasn't sure of.

Now I can see what they are asking, and that you are thinking well (though you at first said you wrote the proof, and then the second time you seem to say it is someone else's proof that you don't fully understand, so I'm a little confused).


I'm not sure what you are asking here. The point of the proof is that the number of ways to cover the whole board is the sum of the ways to cover the middle part (between A and B) in each case. So what happens between them matters very much.

If you're asking, why did they choose to focus on the start and end of the board, that's probably just because this is the identity they wanted you to end up with! In combinatorics, you can look at just about anything in more than one way, and which ways you choose determine what you will see.