MHB Solve Recurrence Equation for Domino Chart of 1xn

[Puzzles]

Hey everyone, it's me again with yet another recurrence equation I've been stuck with:

Using recurrence relations (recurrence equations... is it the same thing?), solve the following: There is a chart with dimensions 1xn. We have dominoes in two different colors which we should use to fill up the chart. In how many different ways can the chart be filled?

The way I understand it, a single domino will take up two spaces. Therefore, we have n/2 places to put the dominoes in, and 2 choices at each place. However, I'm not certain about the whole "a single domino will take up two spaces" if it's a correct assumption at all - I'm afraid I don't understand the problem well enough. In any case, if this is the solution, it has nothing to do with recurrence relations, and I have no idea how to even start with those.

Very obviously, I'm hopeless with recurrence problems. I hope someone can explain how this particular problem should be solved using recurrence relations. Thank you :)

 

[I like Serena]

Hey everyone, it's me again with yet another recurrence equation I've been stuck with:

Using recurrence relations (recurrence equations... is it the same thing?), solve the following: There is a chart with dimensions 1xn. We have dominoes in two different colors which we should use to fill up the chart. In how many different ways can the chart be filled?

The way I understand it, a single domino will take up two spaces. Therefore, we have n/2 places to put the dominoes in, and 2 choices at each place. However, I'm not certain about the whole "a single domino will take up two spaces" if it's a correct assumption at all - I'm afraid I don't understand the problem well enough. In any case, if this is the solution, it has nothing to do with recurrence relations, and I have no idea how to even start with those.

Very obviously, I'm hopeless with recurrence problems. I hope someone can explain how this particular problem should be solved using recurrence relations. Thank you :)

Hey Puzzles,

Suppose $a_n$ is the number of ways for a chart with $n$ positions and $n$ even.
In how many ways might we insert another domino between the others, giving us a chart of $n+2$ positions?
And what does that make $a_{n+2}$? (Wondering)

 

[MarkFL]

In my opinion, this is the most poorly constructed problem I've seen in quite some time (shame on whoever assigned this to students). Why were dominoes used, where one must assume $n$ is even if we assume the dominoes are 1 X 2? Why is there no mention of the type of domino sets, such as double-six sets or double-nine sets? If we have two double-$p$ sets, then must we assume $n=(p+1)(p+2)$? Can the dominoes be placed pip side up or down?

A better problem to me would be to use 1 X 1 solidly colored square tiles, with a choice of 2 or even $m$ colors, where the number of tiles of any particular color from which to choose is at least as great as $n$. :D

 

[Puzzles]

I agree that it's an awfully constructed problem, honestly I'm not even sure I understand it. Somehow I got to solve it in the next few hours.

I've been thinking about it a lot. Let's say one domino is blue, the other is green.

1 x 1: 0
1 x 2: 2 different ways, we can place the blue one, or the green one
1 x 3: 4 different ways, but it gets tricky - we haven't exactly filled the entire board.
1 x 4: again 4 different ways, but this isn't too difficult to picture. We either have 2 blue, 2 green, 1st blue then green, or 1st green then blue
1 x 5: 12 ways
1 x 6: here's where I count 8, and get really confused
View attachment 6556
View attachment 6557

I don't think that what I'm doing with the odd numbers is correct. If we consider n to be even, then, with combinatorics, I get 2^n/2, which is exactly what I've been counting with my visualization. I still don't understand if a domino will take up two spots in the chart, or one. Even in the case I've presented, the relation a_n = 2a_n-2 leaves me uncertain.

 

[MarkFL]

If we assume the dominoes are 1 X 2, and we assume there will be no blank spaces (i.e. the chart is completely filled), then we must assume $n$ is even. Let $n=2k$ where $k\in\mathbb{N}$.

We should further assume that pips are to be ignored, or don't come into play, that is, we simply have 1 X 2 solidly colored tiles.

So far you have found, in terms of $a_k$:

$$a_1=2$$

$$a_2=4$$

$$a_3=8$$

Now, what relation would you say there is between $a_k$ and $a_{k-1}$? Can you state a reason for the relationship that doesn't rely on knowing any particular $a_k$?

 

[Puzzles]

If we assume the dominoes are 1 X 2, and we assume there will be no blank spaces (i.e. the chart is completely filled), then we must assume $n$ is even. Let $n=2k$ where $k\in\mathbb{N}$.

We should further assume that pips are to be ignored, or don't come into play, that is, we simply have 1 X 2 solidly colored tiles.

So far you have found, in terms of $a_k$:

$$a_1=2$$

$$a_2=4$$

$$a_3=8$$

Now, what relation would you say there is between $a_k$ and $a_{k-1}$? Can you state a reason for the relationship that doesn't rely on knowing any particular $a_k$?

a_k = 2a_k-1. Same as a_k = 2^n/2, which doesn't rely on the previous solution. I have trouble trusting this solution...

 

[MarkFL]

a_k = 2a_k-1. Same as a_k = 2^n/2, which doesn't rely on the previous solution. I have trouble trusting this solution...

I agree that:

$$a_k=2a_{k-1}$$

My reasoning would be:

$$a_k=(\text{number of color choices})\cdot a_{k-1}$$

Each time we add a tile, we have 2 choices of color, and so we double the previous number of ways to tile the chart. And so we have the recurrence:

$$a_k=2a_{k-1}$$ where $a_1=2$

Can you now find the closed form for $a_k$?

 

[Puzzles]

I'm sorry, I'm not sure I know what "closed form" refers to.

 

[MarkFL]

I'm sorry, I'm not sure I know what "closed form" refers to.

Typically, when you solve a recurrence relation (difference equation), you turn the relationship between successive values of the recurrence into a function that doesn't depend on previous values. This may also be referred to as solving the recurrence. :D

So, what we want is something of the form:

$$a_k=f(k)$$

where $f$ depends only on $k$, and not other values of $a$.

 

[Puzzles]

Typically, when you solve a recurrence relation (difference equation), you turn the relationship between successive values of the recurrence into a function that doesn't depend on previous values. This may also be referred to as solving the recurrence. :D

So, what we want is something of the form:

$$a_k=f(k)$$

where $f$ depends only on $k$, and not other values of $a$.

Oh, right, thanks! Isn't it simply a_k = 2^k/2?

 

[MarkFL]

Oh, right, thanks! Isn't it simply a_k = 2^k/2?

Well, let's see...the characteristic equation is:

$$r-2=0\implies r=2$$

And thus, the closed form will take the form:

$$a_k=c_12^k$$

Now, we must use our initial value to determine the parameter $c_1$:

$$a_1=2c_1=2\implies c_1=1$$

And so the solution to the recurrence is:

$$a_k=2^k$$ where $k=\frac{n}{2}$

 

[Puzzles]

Yeah, exactly! My approach is never mathematical enough. Thanks a bunch, again!

 

[Puzzles]

Update: I had a talk with the professor today, and turns out there was a typo in the assignment - the board is supposed to be 2xn, not 1xn as it was written. She also confirmed we're considering 1x2 sized dominoes.

I've found several solutions online, which look pretty much the same like the one here: Fit 1*2 dominos in 2*N strip | PROGRAMMING INTERVIEWS

So yeah. Now I'm just trying to get around the "two different colors" problem. Does anyone have any ideas how to do this with two different sets of dominoes?

 

[MarkFL]

Based on the reasoning in the link posted, and extending it to tiles of two colors, I would posit the recurrence:

$$a_{n+1}=2a_{n}+4a_{n-1}$$ where $$a_1=2,\,a_2=4$$

So, can you find the characteristic roots and give the general form for the solution?

 

[Puzzles]

How did you come to that recurrence?

For the roots, I get 1+sqrt(5) and 1-sqrt(5). (I still can't figure out how to format it properly, I'm sorry :( I keep trying to)

Based on this, I get:

a_n = (1+sqrt(5))ⁿ + (1-sqrt(5))ⁿ

 

[MarkFL]

How did you come to that recurrence?

If $F_n$ is the $n$th Fibonacci number, then I considered:

$$a_{n}=2^nF_{n}\implies F_n=2^{-n}a_{n}$$

But, we know:

$$F_{n+1}=F_{n}+F_{n-1}$$

And so we may write:

$$2^{-(n+1)}a_{n+1}=2^{-n}a_{n}+2^{-(n-1)}a_{n-1}$$

Multiply through by $2^{n+1}$ to get:

$$a_{n+1}=2a_{n}+4a_{n-1}$$

For the roots, I get 1+sqrt(5) and 1-sqrt(5). (I still can't figure out how to format it properly, I'm sorry :( I keep trying to)

Based on this, I get:

a_n = (1+sqrt(5))ⁿ + (1-sqrt(5))ⁿ

Yes, those are the correct roots, however, this means the general form of the solution will be:

$$a_n=c_1\left(1+\sqrt{5}\right)^n+c_2\left(1-\sqrt{5}\right)^n$$

Now, we need to determine the parameters $c_i$ from the initial values...(Thinking)

 

[Puzzles]

Oh thanks, that makes a lot of sense. And yeah, I just wrote it down directly because I got c₁ = c₂ = 1.

 

[MarkFL]

Oh thanks, that makes a lot of sense. And yeah, I just wrote it down directly because I got c₁ = c₂ = 1.

I get different values...please post your work so I can see where we differ. :)

 

[Puzzles]

Well,

a₁ = 2 = c₁(1+sqrt(5)) + c₂(1-sqrt(5))
a₂ = 4 = c₁(1+sqrt(5))² + c₂(1-sqrt(5))²

c₁ + c₁sqrt(5) + c₂1 - c₂sqrt(5) = 2
6c₁ + 2c₁sqrt(5) + 6c₂1 - 2c₂sqrt(5) = 4

When I multiply the first equation by 2, and subtract it from the second, I get

c₁ = c₂

And, replacing that in the first equation,

2c₁ = 2

Thus
c₁ = c₂ = 1

- - - Updated - - -

Well,

a₁ = 2 = c₁(1+sqrt(5)) + c₂(1-sqrt(5))
a₂ = 4 = c₁(1+sqrt(5))² + c₂(1-sqrt(5))²

c₁ + c₁sqrt(5) + c₂1 - c₂sqrt(5) = 2
6c₁ + 2c₁sqrt(5) + 6c₂1 - 2c₂sqrt(5) = 4

When I multiply the first equation by 2, and subtract it from the second, I get

c₁ = c₂

And, replacing that in the first equation,

2c₁ = 2

Thus
c₁ = c₂ = 1

Right, I see my mistake now.

c₁ = -c₂

So, c₁ = 1/sqrt(5), c₂ = -1/sqrt(5)

 

[MarkFL]

Well,

a₁ = 2 = c₁(1+sqrt(5)) + c₂(1-sqrt(5))
a₂ = 4 = c₁(1+sqrt(5))² + c₂(1-sqrt(5))²

c₁ + c₁sqrt(5) + c₂1 - c₂sqrt(5) = 2
6c₁ + 2c₁sqrt(5) + 6c₂1 - 2c₂sqrt(5) = 4

When I multiply the first equation by 2, and subtract it from the second, I get

c₁ = c₂

What you actually get is:

$$c_1=-c_2$$

This is what you get if you consider the case where $n=0$...which is $a_0=0$.

So, using $a_1$, we then have:

$$c_1(1+\sqrt{5})-c_1(1-\sqrt{5})=2$$

What do you now get for $c_1$?

 

[MarkFL]

Right, I see my mistake now.

c₁ = -c₂

So, c₁ = 1/sqrt(5), c₂ = -1/sqrt(5)

Yes, that's what I got as well. (Yes)

As a follow-up question, using your result and the relationship between this sequence and the Fibonacci sequence, what would be the closed form for the Fibonacci sequence?

 

[Puzzles]

Yeah, I'm a little popular in my uni for screwing up at least a quarter points of each exam by making silly mistakes like that. :D

a_n = 1/sqrt(5)(1+sqrt(5))ⁿ - 1/sqrt(5)(1-sqrt(5))ⁿTo the follow up question, I get the same result... :( My gut tells me I'm just solving it wrong, as usual. The roots are 1/2 + 1/2sqrt(5) and 1/2 - 1/2sqrt(5) this time. Considering that a₁ = 1 and a₂ = 2 in this case, I get the same result... I'm sorry for being useless. My problem is I haven't solved nearly enough examples to actually know what I'm doing, which is due to the fact that education over here sucks.

 

[MarkFL]

Yeah, I'm a little popular in my uni for screwing up at least a quarter points of each exam by making silly mistakes like that. :D

a_n = 1/sqrt(5)(1+sqrt(5))ⁿ - 1/sqrt(5)(1-sqrt(5))ⁿ

Yes, and I would write this as:

$$a_n=\frac{\left(1+\sqrt{5}\right)^n-\left(1-\sqrt{5}\right)^n}{\sqrt{5}}$$

To the follow up question, I get the same result... :( My gut tells me I'm just solving it wrong, as usual. The roots are 1/2 + 1/2sqrt(5) and 1/2 - 1/2sqrt(5) this time. Considering that a₁ = 1 and a₂ = 2 in this case, I get the same result... I'm sorry for being useless. My problem is I haven't solved nearly enough examples to actually know what I'm doing, which is due to the fact that education over here sucks.

For this, I would observe that we previously found:

$$F_n=2^{-n}a_n$$

Using our closed form for $a$, we obtain:

$$F_n=2^{-n}\left(\frac{\left(1+\sqrt{5}\right)^n-\left(1-\sqrt{5}\right)^n}{\sqrt{5}}\right)=\frac{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}}$$

A special number in mathematics is called the golden ratio, and is given as:

$$\varphi=\frac{1+\sqrt{5}}{2}$$

Now, it can algebraically be shown that:

$$\frac{1-\sqrt{5}}{2}=-\varphi^{-1}$$

And so we can state the closed form for the Fibonacci sequence in terms of $\varphi$ as follows:

$$F_n=\frac{\varphi^n-(-\varphi)^{-n}}{2\varphi-1}$$

And thus, we can express our sequence in terms of $\varphi$ as:

$$a_n=\frac{(2\varphi)^n-\left(-\dfrac{\varphi}{2}\right)^{-n}}{2\varphi-1}$$