Problem of the Day #2: Problem 37 Section 5.1

In this problem we are given Red, Green and Gray tiles. We are to arrange them in a line to make sidewalks (or whatever). We are to compute the number of distinct walkways of length n which can be made without allowing two successive Red tiles.

Set a_n to be this number. We would like to find a recurrence relation for the sequence of a_n's. Think about building such a walkway (and have in mind that we have at our disposal all good walkways of shorter length).

If we place a tile in the first position, that of course leaves us with n-1 positions to fill. The next n-1 positions constitute a walkway with n-1 tiles of course. Clearly this shorter walkway is not permitted to have two successive Red tiles, so it is one of the a_(n-1) many good walkways of length n-1. If the first tile is not Red then we can put any one of these shorter walkways down and the result will be a good walkway. Well this accounts for 2*a_(n-1) many walkways of length n - namely all those that start with either a Green or Gray tile.

Now let's count the walkways that start with a Red tile. This is different because we cannot just stick any length n-1 walkway after this tile because we may get 2 successive Reds. So obviously we have to either put a Green or a Gray tile next. Following that we can certainly put any length n-2 tile AND conversely every walkway that starts out RED GREEN is followed by a length n-2 good walkway. Similarly for RED GRAY starting walkways. Therefore there are a_(n-2) good walkways that start RED GREEN and an equal number that start RED GRAY.

Finally our desired recurrence relation is: a_n = 2*a_(n-1) + 2*a_(n-2)

The initial conditions are a_0 = 1 and a_1=3 since there is exactly 1 walkway with no tiles and exactly 3 with 1 tile.

What is a_7? Well just start churning out the terms:
a_2 = 2*a_1 + 2*a_0 = 2*3+2*1 = 8

    
a_3 = 2*a_2+2*a_1 = 2*8+2*3=22
a_4=2*22+2*8=44+16=60
           
a_5 = 2*60+2*22=120+44=164
a_6=2*164+2*60=328+120=448
       
a_7=2*448+2*164= 896+328= 1224

Well what are we learning next? This recurrence relation, a_n = 2*a_(n-1)+2*a_(n-2), has characteristic equation: r^2 - 2*r - 2= 0. This characteristic equation has two distinct roots or solutions. Just use the quadratic formula: the solutions to ax^2 + bx + c = 0 are given by the formula: (-b +/- SQRT(b^2 - 4ac) )/2a. In our case a=1, while b=c=2. So the solutions are -(-2) + SQRT((-2)^2-4*(-2) )/2 and -(-2) - SQRT( (-2)^2-4*(-2) )/2. These simplify to
r_1 = 1 + SQRT(3)

        and      
r_2 = 1 - SQRT(3)

Very important, any solution to the characteristic equation yields a solution to the recurrence relation by just taking its powers. I.e. { (1+SQRT(3))^n } for n = 0,1,2,... is a solution

AND
{ ( 1-SQRT(3))^n } for n = 0,1,2,... is another solution.

Why is that true? Simply if r is a solution to r^2 - 2r - 2 =0, then clearly r has the property that

r^2 = 2*r + 2

    hence   
r^n = 2 * r^(n-1) + 2 * r^(n-2)
since all we did was to multiply both sides by r^(n-2). But this means that the sequence of powers of r is a solution to the recurrence relation. This is true for the sequence of powers of r_1 and for the sequence of powers of r_2.

Also, as we discovered, if we add two solutions together we get more solutions. In fact if we pick any two real numbers, call them A and B, (or even complex numbers), then
{ A*r_1^n + B * r_2^n } is yet another solution. We finish solving this recurrence relation by finding suitable values for A and B so that we also get the right initial conditions.

That is we want: a_0 = 1 and a_1 = 3. Set up the required two equations:

a_0 = 1 = A * (r_1)^0 + B * (r_2)^0 = A + B

and

a_1 = 3 = A * (r_1)^1 + B * (r_2)^1 = A*r_1 + B*r_2

Remember that r_1 and r_2 are known values (above) and we want to solve for A and B. Take the second equation and subtract r_2 times the first equation (this will eliminate the B term):

3 - r_2*1 = ( A*r_1 - r_2*A ) + ( B * r_2 - r_2 * B ) = A * (r_1 - r_2)

     hence

A = (3 - r_2 ) / (r_1 - r_2) (we are using that r_1 is not equal to r_2). Plug this value for A into one of the equations (easiest to use the first) and solve for B.

1 = A + B hence B = 1 - (3 - r_2) / (r_1 - r_2) = ( (r_1 - r_2 ) - (3 - r_2 ) ) / (r_1 - r_2) = ( r_1 - 3) / (r_1 - r_2). Well finally plug in for r_1 = 1 + SQRT(3) and r_2 = 1 - SQRT(3). This give us the real numerical values for A and B which we plug back into the equation: a_n = A * (r_1)^n + B * (r_2)^n . Since r_1 - r_2 = 2*SQRT(3):

A = (3 - r_2 ) / (r_1 - r_2) = ( 3 - (1-SQRT(3) )/ (2*SQRT(3)) = ( 2 + SQRT(3) ) / (2*SQRT(3))

     and   
B = ( (1+SQRT(3))-3)/ (2*SQRT(3)) = (SQRT(3) -2)/( 2*SQRT(3)).

Hence

      (2 + SQRT(3)) * (1+SQRT(3))^n    +   (SQRT(3) -2) * (1-SQRT(3))^n 
a_n =  -------------                        ------------                
       (2*SQRT(3))                          (2*SQRT(3))
Go ahead plug in n=0 and n=1 to be sure we get a_0 = 1\ and a_1=3.

Let's try a_7: (1+SQRT(3))^7 = 1136.1127 and (1-SQRT(3))^7 = -0.1127. Also A = 1.0774 and B = -0.0774, so finally:

A (r_1)^7 + B (r_2)^7 = (1.0774)*(1136.1127) + (-0.0774)*(-0.1127) = 1224.0565

I guess my calculator has round off errors.