{VERSION 5 0 "IBM INTEL NT" "5.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 
1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 
0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }
{CSTYLE "" -1 256 "Helvetica" 1 14 128 0 0 1 0 0 2 0 0 0 0 0 0 1 }
{CSTYLE "" -1 257 "" 0 24 0 0 255 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" 
-1 258 "Helvetica" 0 1 128 0 0 1 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 
259 "" 0 1 255 0 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 
0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 0 1 0 0 128 1 0 0 0 
0 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 1 12 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 273 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
274 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 
0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 1 0 0 0 0 
0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 278 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
279 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 0 1 0 0 
0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 0 1 0 0 0 0 
0 0 0 0 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 283 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
284 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 285 "" 0 1 0 0 
0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 286 "" 0 1 0 0 0 0 0 1 0 0 0 0 
0 0 0 0 }{CSTYLE "" -1 287 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }
{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 
2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 1" -1 3 1 
{CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 
4 1 0 1 0 2 2 0 1 }{PSTYLE "Title" -1 256 1 {CSTYLE "" -1 -1 "Times" 
1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }1 1 0 0 12 12 1 0 1 0 2 2 19 1 }
{PSTYLE "Author" -1 257 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 
2 2 2 1 1 1 1 }1 1 0 0 8 8 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 258 1 
{CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 0 
0 1 0 1 0 2 2 0 1 }{PSTYLE "Title" -1 259 1 {CSTYLE "" -1 -1 "Times" 
1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 }
{PSTYLE "Author" -1 260 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 1 
2 2 2 1 1 1 1 }3 1 0 0 8 8 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 261 1 
{CSTYLE "" -1 -1 "Courier" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 
0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 262 1 {CSTYLE "" -1 -1 "Times
" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 }
{PSTYLE "Normal" -1 263 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 2 2 
2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 264 1 
{CSTYLE "" -1 -1 "Courier" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 
0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2" -1 265 1 {CSTYLE "" -1 -1 "Ti
mes" 1 12 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 2 1 0 1 0 2 2 0 1 }}
{SECT 0 {EXCHG {PARA 256 "" 0 "" {TEXT 257 30 "MLC Lab Visit - Lab 05 \+
- Maple" }}{PARA 0 "" 0 "" {TEXT 256 46 "Mth 355 (a.k.a. Mth 399) Feb \+
05, 2003  Maple 7" }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 258 16 "Bent
 E. Petersen" }{TEXT -1 0 "" }}{PARA 264 "" 0 "" {TEXT 260 0 "" }}
{PARA 264 "" 0 "" {TEXT 261 22 "petersen@math.orst.edu" }}{PARA 0 "" 
0 "" {TEXT -1 0 "" }}{PARA 263 "" 0 "" {TEXT 259 181 "There are 6 prob
lems below. Problem solutions are due Feb 12, 2003. Email your solutio
ns to me as Maple worksheet attachments. Your worksheet must execute c
orrectly for full credit." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 1 
{PARA 3 "" 0 "" {TEXT -1 50 "Linear Recurrence Equations - Generating \+
Functions" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 272 0 "" }}{PARA 0 "" 0 "
" {TEXT -1 134 "We considered already, a little bit, the generating fu
nction of a recurrence relation in lab 04. This section therefore is r
epetition." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 
-1 231 "The Maple function rsolve() is used to solve linear recurrence
 relations. It can also be used to find the generating function of the
 solution to a linear recurrence relations. Consider the example (base
d on the Fibonacci sequence):" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "eqn1:=a(n)=a(n-1)+a(n-2)+(-1
)^n*n; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "init1:=a(0)=0,a(
1)=1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "g1:=rsolve(\{eqn1,
init1\},a,'genfunc'(z));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 65 "Note the single quotes surrounding  genfu
nc in the command above." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "
" 0 "" {TEXT -1 116 "Once we have the generating function we can find \+
the a(n)  by computing the Taylor series with center at the origin." }
}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 18 "taylor(g1,z=0,21);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 59 "Of course Maple will also find a procedur
e to compute a(n):" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 39 "fn1:=rsolve(\{eqn1,init1\},a,'makeproc'):" 
}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 95 
"Let's compute  a(20)  and compare it with the coefficient of  z^20  i
n the Taylor series above:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "fn1(20); simplify(%); rationalize(%
);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 
-1 167 "As you can see, Maple can be a little stuborn when it comes to
 giving us the answer in the form that we want, even when it is an int
eger. You just have to keep trying!" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }
}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 130 "Note we do not have to rely on \+
our eyesight to extract the coefficient of  z^20  in the Taylor series
 - Maple will find it for us:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "subs(z=0,diff(g1,z$20))/20!;
" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 
73 "The expression  z$20  here generates a sequence of  20  z's - very
 handy!" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 5 "z$20;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }
}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 60 "Graphs. Adjacency Matrix. Numb
er of Paths of a Given Length." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "
" }}{PARA 0 "" 0 "" {TEXT -1 153 "Graphs are supported in Maple by the
 networks package. Use the command  ?networks  to get help on the vari
ous procedures defined in the networks package." }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "with(networks): with(linalg
):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 279 9 "Example 1" }}{PARA 0 "" 0 "
" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 95 "The  new()  command cre
ates a graph with an empty set of vertices and an empty set of vertice
s." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 8 "new(G1):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 64 "We can add vertices to our graph with the
  addvertex()  command:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "addvertex([v1,v2,v3,v4],G1);" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 288 "W
e add edges by specifying their set or list of endpoints (in a list). \+
If we do not provide names for the edges then the default names  e1, e
2,  and so on, will be used. If we use sets of endpoints we obtain und
irected edges, whereas if we use lists of endpoints we obtain directed
 edges." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 74 "addedge([\{v1,v2\},\{v2,v3\},\{v3,v1\},\{v3,v4\}],nam
es=[edg1,edg2,edg3,edg4],G1);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "
" }}{PARA 0 "" 0 "" {TEXT -1 115 "Maple can draw graphs though the rou
tine provided is a bit primitive. We can not specifiy color nor line t
hickness." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 9 "draw(G1);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }
}{PARA 0 "" 0 "" {TEXT -1 154 "We can exercise some control over the s
hape of the drawn graphs, but it is limited. Check Maple help for the \+
details of the Concentric and Linear options." }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "draw(Concen
tric([v1,v2,v4],[v3]),G1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
33 "draw(Linear([v1,v3],[v2,v4]),G1);" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 142 "The adjacency matrix tel
ls which vertices are joined by edges:  M1[i,j] = 1  if there is an ed
ge joining  vi  and  vj. Otherwise  M1[i,j] = 0." }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "M1:=adjacen
cy(G1);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 280 9 "Example 2" }}{PARA 0 "
" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 71 "The complete graph
 has an undirected edge joining each pair of vertices" }}{PARA 0 "" 0 
"" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "G2:=comp
lete(5):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "vertices(G2);" 
}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "edges(G2);" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "draw(G2);" }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 18 "M2:=adjacency(G2);" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT 281 9 "Example 3" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 
0 "" {TEXT -1 190 "A loop at a vertex v, that is, an edge joining  v  \+
to itself,  is specified as  \{v\}. Unfortunately, the  draw()  comman
d will choke on graphs containing loops, or will not display the loops
." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 8 "new(G3):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 
"addvertex(v1,v2,G3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "ad
dedges([\{v1,v2\},\{v2\}],G3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "
" }}{PARA 0 "" 0 "" {TEXT -1 71 "The ends command will list the vertic
es which form the ends of an edge:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "ends(e1,G3);" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "ends(e2,G3);" }}}{EXCHG {PARA 0 "" 
0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 71 "The adjancency matri
x in the presence of loops has 2's on the diagonal." }}{PARA 0 "" 0 "
" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "M3:=adjac
ency(G3);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 92 "Sometimes one wants the loops to count only as 1, not as \+
2. We can take care of that easily:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "evalm(M3-diag(seq(M3[i,i]/
2,i=1..coldim(M3))));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 120 "Make sure you understand how the previou
s command works. It is writetn so as to work for adjacency matrices of
 any size." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT 282 9 "Example 4" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 
0 "" {TEXT -1 48 "The petersen graph (no relation) is interesting:" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 15 "G4:=petersen():" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "dra
w(G4);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "M4:=adjacency(G4)
;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 
153 "The eigenvalues of the adjacency matrix can tell us quite a bit a
bout a graph. In the case of the petersen graph the eigenvalues are pa
rticularly simple." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 14 "eigenvals(M4);" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT 283 9 "Example 5" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 
0 "" {TEXT -1 39 "Here's a graph with two directed edges:" }}{PARA 0 "
" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "new(G
5):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "addvertices([v1,v2,v
3,v4,v5],G5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 71 "addedges([
\{v1,v2\},[v1,v3],[v3,v5],\{v1,v4\},\{v4,v5\},\{v2,v5\},\{v3,v4\}],G5)
;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "draw(G5);" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 94 "Unfortuna
tely the draw command does not indicate direction. The adjacency matri
x does however:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 18 "M5:=adjacency(G5);" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 211 "Note we have a directed \+
edge from v1 to v3 so  M5[1,3] = 1  but  M5[3,1] = 0. Think of directe
d edges as one-way streets. Because of the directed edges  M5  is not \+
symmetric. Nonetheless it has real eigenvalues:" }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "eigenvals(M
5);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 
-1 68 "We may wonder if M5 is diagonizable, but then we run into a pro
blem:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 14 "is(M5,matrix);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 
"" }}{PARA 0 "" 0 "" {TEXT -1 240 "It appears the data structure retur
ned by the  adjacency()  command is not recognized as a matrix by Mapl
e! Fortunately we can force Maple to view it as a matrix by using the \+
 evalm()  command. We can then compute the Jordan canonical form:" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 18 "jordan(evalm(M5));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 36 "We see that M5 is not diagonizable. " }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 284 9 "E
xample 6" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 
98 "Consider a simple graph, that is, a graph with no parallel edges, \+
no loops, and no directed edges." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "new(G6):" }}}{EXCHG {PARA 0 "
> " 0 "" {MPLTEXT 1 0 28 "addvertices(v1,v2,v3,v4,G6);" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "addedges([\{v1,v2\},\{v1,v3\},\{v1,
v4\},\{v2,v3\},\{v3,v4\}],G6);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 9 "draw(G6);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "M6:=adj
acency(G6);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "
" {TEXT -1 84 "Now  M6  is a real symmetric matrix, so it has real eig
envalues and is diagonizable." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "eigvals:=eigenvals(M6);" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 288 "C
onsider now a path in  G6  where we walk along successive edges. The l
ength of a path is the number of edges in it. It takes only a moment o
f reflection to realize that the number of paths of length  n  from th
e  ith  to the  jth  vertex is the  (i,j)th  entry in the matrix  M6^n
. Since" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 6 "M6^20;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 189 "we see there are  45,954,543  paths of l
ength   20  from   v1  to  v1. (Can you see all of them?) This result \+
is nice but not very convenient if we want to know how many paths of l
ength  n." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 
84 "If we diagonalize  M6  we can obtain a convenient formula with a l
ittle bit of work." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 27 "T6:=jordan(evalm(M6),'P6');" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 4 "Note" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 47 "evalm( P6 &* T6 &* P6^(-1) - M6 ): simplify(%);" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 90 "It follow
s that  M6^n = P6 &* T6^n &* P6^(-1). Let's introduce a symbolic versi
on of  T6^n" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 58 "T6n:=diag(op(map(x->x^n,[seq(T6[i,i],i=1..coldim(T
6))])));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 48 "(Make sure you understand the previous command.)" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 21 "Then M6^n
 is given by" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 27 "M6n:= P6 &* T6n &* P6^(-1):" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 32 "Now for the (1,1) \+
entry we have:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 20 "np:=evalm(M6n)[1,1];" }}}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 112 "This then is the numbe
r of paths of length  n  from  v1  to  v1. Let's check it agrees with \+
the above for  n=20." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 27 "subs(n=20,np): simplify(%);" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 12 "Sure enou
gh." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 0 "" }}}}{SECT 1 {PARA 3 "" 0 "" {TEXT -1 8 "Problems" }}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 273 9 "Problem 1" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 38 "Find the \+
generating function  g   for " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "a:=n->sum(k^5,k=0..n);" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 287 5 "Hi
nt:" }{TEXT -1 94 " Find a recurrence equation (and initial condition)
 satisfied by  a(n)  and then use rsolve()." }}{PARA 0 "" 0 "" {TEXT 
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 93 "As a check the coefficient of  \+
z^17  in the Taylor-Maclaurin expansion of  g(z)  is  a(17) = " }
{XPPEDIT 18 0 "4767633;" "6#\"(Lww%" }{TEXT -1 1 "." }}{PARA 0 "" 0 "
" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 274 9 "Problem 2" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 36 "Find the \+
generating function  g  for" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "eqnp2:=b(n)=6*b(n-1)+3*4^n;
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "initp2:=b(0)=2;" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 276 9 "Pr
oblem 3" }{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "unassign('a');" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 275 0 "" }{TEXT -1 32 "Co
nsider the recurrence equation" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "eqnp3:=a(n)=n*a(n-1);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "initp3:=a(0)=1;" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 135 "The solu
tion to this recurrence equation is pretty obvious, but if you ask Map
le to compute the generating function, Maple chokes. Why?" }}{PARA 0 "
" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 
0 "" 0 "" {TEXT 277 9 "Problem 4" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 61 "Find the generating function  gp4 for the
 recurrence equation" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 23 "eqnp4:=b(n)=b(n-3)+4*n;" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 30 "initp4:=b(0)=0,b(1)=0,b(2)=-1;" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 16 "Then find b(20)." }}{PARA 0 "" 0 "
" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 278 9 "Problem 5" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 228 "Write a \+
procedure  taylorcoeff(g,n,z)  to return the the nth coefficient in th
e Taylor-Maclaurin expansion of an expression  g. Write your procedure
 so the variable relative to which to expand is specified as the third
 argument." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 
-1 23 "As a check on your work" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 53 
"        taylorcoeff(1/(3*z+w^3), 15, z);   returns   " }{XPPEDIT 18 
0 "-14348907*1/(w^48);" "6#,$*&\"\"\"F%*$)%\"wG\"#[F%!\"\"!)2*[V\"" }
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 
-1 53 "        taylorcoeff(1/(3*z+w^3), 15, w);   returns   " }
{XPPEDIT 18 0 "-1/729;" "6#,$*&\"\"\"F%\"$H(!\"\"F'" }{TEXT -1 2 "  " 
}{XPPEDIT 18 0 "1/(z^6);" "6#*&\"\"\"F$*$)%\"zG\"\"'F$!\"\"" }{TEXT 
-1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "with(networks): w
ith(linalg):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "
" {TEXT 285 9 "Problem 6" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "
" 0 "" {TEXT -1 27 "Consider the  2 by 2 matrix" }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "Mp6:=matrix
(2,2,[0,1,1,1]);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "
" 0 "" {TEXT -1 6 "Notice" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "evalm(Mp6^2); evalm(Mp6^3); evalm(M
p6^4);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 202 "Clearly a simple induction will show that  Mp6^n[2,2]  i
s the  nth  Fibonacci number (assuming the 0th and first are  1). By d
iagonalizing  Mp6  deduce the Binet formula for the  nth  Fibonacci nu
mber. " }{TEXT 286 5 "Hint:" }{TEXT -1 46 " See example 6 in the secti
on on graphs above." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 
0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 87 "Problems dealin
g with graphs are postponed until we have developed this topic in clas
s." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{EXCHG {PARA 0 "
> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 3 0" 0 }{VIEWOPTS 1 1 0 1 1 
1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }