URL http://www.mast.queensu.ca/~helena/linal11s2.html

Assignment 6, Solution to problem 2

Problem 2

We have carriages of lengths 2 and 3.

Find a forumlar for the number of trains of length n that can be made from these carriages.

Note, this problem is very similar to the problem about trains described in lecture 11.

We need to work out what the relation is between tn and tn-1, tn-2 and tn-3.

It might help to draw more of the table:
Length of train (n)types of train number of types
1 none 0
2 [AA], [BB]2
3 [CCC] 1
4
[AA][AA][AA][BB]
[BB][AA][BB][BB]
4
5
[AA][CCC]
[BB][CCC]
[CCC][AA],[CCC][BB]
4
6
[AA][AA][AA][AA][AA][BB]
[AA][BB][AA][AA][BB][BB]
[BB][AA][AA][BB][AA][BB]
[BB][BB][AA][BB][BB][BB]
[CCC][CCC]
9

To build a train of length n, we look at what it's head can be. There are three choices:

[*****************train length n**************]
comes with the following heads:
[AA][*************train length n-2************]
[BB][*************train length n-2************]
[CCC][************train length n-3************]

We want to find some relationship between the trains of lengh n and trains of shorter length.

There are tn-2trains of length n-2, so

So in total that means there are tn-2+tn-2+tn-3 trains of length tn.

So we have

tn-3=0tn-1+2tn-2+tn-3

The next thing to do is get a matrix equation. We can do this by getting equations for (tn,tn-1,tn-2) in terms of (tn-1,tn-2,tn-3). We get the following:

tn=0tn-1+2tn-2+tn-3
tn-1=1tn-1+0tn-2+0tn-3
tn-2=0tn-1+1tn-2+0tn-3

Rewriting this as a matrix and vector equation, we have:

/tn\/021\/tn-1\
|tn-1|=|100||tn-2|
\tn-2/\010/\tn-3/

Next we'll introduce some short hand, xn and A: Let

/tn\/021\
xn=|tn-1|andA=|100|
\tn-2/\010/

Then by sustituting n with n-1, we have

/tn-1\
xn-1=|tn-2|
\tn-3/

So the equation above in shorthand looks like

xn=Axn-1

So xn=A2xn-2, since xn-1=Axn-2

We have x3=(t3,t2,t1), and from the table we made, we know this is (1,2,0).

Then

x3=(1,2,0)
x4=Ax3
x5=Ax4=A(Ax3)=A2x3
x6=Ax5=A(A2x3)=A3x3
x7=Ax6=A(A3x3)=A4x3
x8=Ax7=A(A4x3)=A5x3
x9=Ax8=A(A5x3)=A6x3

Generally, xn=An-3x3.

We can work with this, but we can also define x0, x1 and x2, by defining t0=1 t-1=0 and t-2=0, and we can check that the relationships with the tn also hold for these new tn, and then we get:

x3=A3x0

and since xn=An-3x3, by substitution,

xn=Anx0

To find a formula for xn in terms of n, we need to find how An changes x0. As usual, we do this via eigen values and eigen vectors:

1:Eigen Values.

det(A-LI)=-L3+2L+1
The roots are -1, (1-root(5))/2, (1+root(5))/2, so these are the eigen values.

2:Eigen Vectors:

We have to solve each of the systems with augemented matrices as below:
/121|0\
|110|0|
\011|0/
/-(1-root(5))/221|0\
|1-(1-root(5))/20|0|
\01-(1-root(5))/2|0/
/-(1+root(5))/221|0\
|1-(1+root(5))/20|0|
\01-(1+root(5))/2|0/

Do row reduction as usual, and find that

For eigen value -1, the eigen vector is
/1\
|-1|
\1/
For eigen value T=(1-root(5))/2, the eigen vector is
/T2\
|T|
\1/
For eigen value R=(1+root(5))/2, the eigen vector is
/R2\
|R|
\1/

3: x0 in terms of eigen vectors:

The next thing to do is express the x0 in terms of the eigen vectors. We found that x0=(1,0,0), so we need to solve

a
/1\
|-1|
\1/
+b
/T2\
|T|
\1/
+c
/R2\
|R|
\1/
=
/1\
|0|
\0/

Then

An
/1\
|-1|
\1/
= (-1)na
/1\
|0|
\0/
+Tnb
/T2\
|T|
\1/
+Rnc
/R2\
|R|
\1/

So since xn=(tn,tn-1,tn-2), we have

tn=a(-1)n+bTn+2+cRn+2
Where T=(1-root(5))/2 and R=(1+root(5))/2.

Need to finish this by finding a,b,c explicitly. We can use MatLab to get an answer, or we can work algebraically, and do the reduction by hand. Then we can use things like T2=T+1 and R2=R+1 (check this).

Which ever way you do it you'll get the same answer, though MatLab might have an error in approximating, but this will not be important.

Solving to find a,b,c:

/1 T2R2|1\
|-1T R |0|
\1 1 1 |0/

When we row reduce to echelon, we end up with:

/1 0 0 |1/((1+T)(1+R))\
|0 1 0 |1/((1+T)(T-R))|
\0 0 1 |1/((1+R)(R-T))/

This is equal to

/1 0 0 |1\
|0 1 0 |(2-T)(?)|
\0 0 1 |(2-R)(?)/
(Actually, for speed, I did most of the above with the algebra package "Maple"; (MatLab does not seem so good at handling variables in matrices).) (If you enjoy algebra, and have time, it might be fun to do it all by hand, use things like 1/t=(t-1). Seemed like fun to me anyway, but I've not finished ityet due to lack of time; anyway, it's not important for this course what the ? are in the matrix immediately above; using the values for R and T (T=-0.618 and R=1.618) will be enough for today.)

If you use MatLab, you'll get

/1 0 0 |1\
|0 1 0 |-1.1708|
\0 0 1 |0.1708/
You can check these are the same by substituting the values T=(1-root(5))/2=-0.618 and R=(1+root(5))/2=1.618 in the first one.

So

And so, substituting for a,b,c,T,R, we get:

tn=(-1)n-1.1708(-0.618)n+2+0.1708(1.618)n+2

When we have the formular, we can quickly caluculate for example, the number of trains of length 35

Amazingly enough, when you type in the above, with n=35, MatLab will spit out an answer, and tell you that there are about 922746 trains of length 35 (There is a possible rounding error due to inaccuracies in values used for a,b,c,T,R; I've not yet worked out the order of the inacuracy, anyway, that's not important for this course.)

Solution 1 Back to the Lecture 11 Notes. Solution 3

Please send comments, questions, suggestions, corrections, ideas, to me.

• Welcome Home • Origami •

Queen's Mathematics and Statistics
Queen's University