Dawn Manco

MA 502 Project

1. Show that the set of polynomials , , ,..., ,... where satisfy the identity (***) . In semigroup parlance, this says that the function is an isomorphism between the semigroup of all polynomials under composition and the semigroup of non-negative integers under mulitplication.

> p[0]:=1;

> p[1]:=x;

> for r from 2 to 6 do p[r]:=expand(2*x*p[r-1]-p[r-2]) od;

This came from a previous worksheet that we did and saved. (The day we made the graph 9-9-99)

> p2p3:=expand(subs(x=p[3],p[2]));

> p3p2:=expand(subs(x=p[2],p[3]));

> p2p3-p3p2;

> p[6]-p2p3;

> p[6]-p3p2;

So we see that for the case n=2, m=3 and n=3, m=2 they are the same as .

> p[n]:= 2*x*(p[n-1]) - p[n-2];

> p[m]:= 2*x*(p[m-1]) - p[m-2];

> p[m*n]:=2*x*(p[m*n-1]) - p[m*n-2];

> p1p2:= expand(subs(x=p[2],p[1]));

> p2p1:=expand(subs(x=p[1],p[2]));

> p2p1 - p1p2;

> p1p2 - p[2];

> p2p1 - p[2];

> p1p3:= expand(subs(x=p[3],p[1]));

> p3p1:= expand(subs(x=p[1],p[3]));

> p1p3 - p[3];

> p3p1 - p[3];

> p1p3 - p3p1;

> pmp1:= expand(subs(x=p[1],p[m]));

> p1pm:= expand(subs(x=p[m],p[1]));

> p1pm - pmp1;

> p1pm - p[m];

> pmp1 - p[m];

As we have seen through these examples, the polynomials commute.

Now we must prove that . This can be done by using to satisfy the identity.

> restart;

> P[n]:= expand(cos(n*arccos(x)));

> for n from 0 to 6 do P[n]:= expand(cos(n*arccos(x))) od;

Through examples, we have shown that P[n] equals p[n] for n = 0..6. Now, we must use mathematical induction to prove the P[n] = p[n] for all n.

(I don't know how to execute this as a maple worksheet so I am going to type it out as text in blue.)

Fine. I prefer that anyway.

= = = , for all n given that and by definition.

In order to prove by induction that for all n , we must use three steps.

1) Show that the formula is true for .

and n = 0

by definition

= cos(0) = 1

so

by definition.

=

2) Assume the formula is true for . and n-1 (this is important, see below)

=

3) Prove that the formula is true for . In doing so will prove the formula to be true for all .

(this is known)

=

= {distribution}

= {substitution with trig Id. (**)}

= {substitution: cos(arccos(x)) = x}

= {substitution: P[n] = cos(n*arccos(x))}

= - *[ ] {sub with trig Id. (***)}

= - *[ ] {simplify}

= - *[ ] (substitution: definition of P[n]}

= - *[ ] {multiply by 2 to cancel 1/2}

= {simplify}

{subtract P[n+1} from both sides}

= (by assumption, note that we need to assume p[n-1] = P[n-1] also)

(**)

(***) = *[ ]

So you have a nice proof, modulo the inserted steps.

QED

We need to prove that . We now see that satisfies the identity. Now we can use to prove .

> restart;

> p[n]:=cos(n*arccos(x));

> p[m]:=cos(m*arccos(x));

We know by definition that . So will ?

> pmpn:=expand(subs(x=p[n],p[m]));

We know from our knowledge of trigonometry that , so = = .

So, in conclusion, does infact equal .