> 9;8Y bjbjWW :==]<G$9-22<<
"Ive looked over the homeworks, and it seems like a large part of the problem is that you sometimes dont know what Im asking you for.
Please dont be shy about sending me email if you feel like you may be missing the point of a question (e.g., if it seems to easy or too hard).
You are more than encouraged to work with each other AND to work with me (i.e., ask me questions by email or in person). Or ask in class.
If you can think of ways the homework problems could be rephrased to make it clearer what the problem is looking for, please let me know.
Also, I urge you to read the solutions. If theyre not clear, let me know! Im assuming that you read these solutions and absorb them. Similar questions may appear on the two exams.
Average scores:
Homework 1: average score: 12.63/20
Homework 2: average score: 13.63/20
Any questions about the homework or the material?
Miscellaneous points to be clarified:
1) The relationship between the generating function approach and the operator approach:
f(x) = a_0 + a_1 x + a_2 x^2 + means (a_0,a_1,a_2,)
x f(x) = 0 + a_0 x + a_1 x^2 + means (0,a_0,a_1,)
(NOT the shift operator T)
On the other hand,
if f means (a_0,a_1,a_2,), i.e., f(x) = a_0 + a_1 x +
then Tf means (a_1,a_2,), i.e., f(x) = a_1 + a_2 x +
So, the linear operator T, expressed in generating-function terms,
means subtract the constant term and divide by x.
2) The relationship between operators and formulas for terms of a sequence:
Say f = (f(0), f(1), f(2), ), whose nth term is f(n)
Then Tf = (f(1), f(2), f(3), ), whose nth term is f(n+1).
So T is also the replace n by n+1 operator, if the terms of the
sequence f are given by some formula.
Example: the sequence (1,3,6,10,).
For n (0, the nth term is given by the formula (n+1)(n+2)/2.
The shifted sequence is (3,6,10,) whose nth term is given by (n+2)(n+3)/2.
The associated generating functions satisfy
3 + 6x + 10x^2 + = ((1 + 3x + 6x^2 + 10x^3 + ) 1) / x
Shorthand notation to use in homework:
T(n) = n+1 [explain what this really means!]
T(n^2) = (n+1)^2
T(2^n) = 2^(n+1)
etc.
2) My treatment of the non-diagonalizable case:
There was a gap in my logic.
I showed that if M is a diagonalizable 2-by-2 matrix with eigenvalues r and s, then for suitable constants A,B,C,D,E,F,G,H,
[Ar^n+Bs^n Cr^n+Ds^n]
M^n = [ ]
[ Er^n+Fs^n Gr^n+Hs^n].
But suppose M is not diagonalizable, with characteristic polynomial p(t) = det(tI-M) = (t-r)(t-r). Then I claimed that, for suitable constants A,B,C,D,E,F,G,H,
[Ar^n+Bnr^n Cr^n+Dnr^n]
M^n = [ ]
[ Er^n+Fnr^n Gr^n+Hnr^n].
Why is this true?
Did anyone think about this?
Well come back to this if theres time.
A powerful theorem that applies here is the Cayley-Hamilton theorem.
Have you seen it before?
It says that if you replace t by M itself in the characteristic polynomial, you get the zero matrix.
Try it for
[2 1]
M = [0 2]: p(t) = (t-2)(t-2)-(1)(0) = t^2 4t + 4.
Lets compute M^2 4M + 4I:
[4 4] [8 4] [4 0] [0 0]
[0 4] [0 8] + [0 4] = [0 0]
Multiplying by M, we get M^3 4M^2 + 4M = 0, too:
[8 12] [16 16] [8 4] [0 0]
[0 8] [ 0 16] + [0 8] = [0 0]
Etc.
So, for instance, if we define f(n) = the upper left entry of M^n, we have f(2) 4f(1) + 4f(0) = 0, f(3) 4f(2) + 4f(1) = 0, etc.
That is, the sequence f(0),f(1),f(2), is annihilated by the linear operator p(T), where p(t) is the characteristic polynomial of M.
Likewise for the other entries.
Likewise for other 2-by-2 matrices.
Likewise for larger matrices, e.g.
[2 1 0]
[0 2 1]
[0 0 2]
Well prove the Cayley-Hamilton theorem later.
3) My treatment of the of linear recurrences for which the associated polynomial has multiple roots.
E.g., T^2 4T + 4I.
How do we know that the general solution is of the form
A 2^n + B n 2^n?
We know that the solution-space is two-dimensional, since the recurrence is second-order, and we can easily check that the sequences (1,2,4,8,16,32,) (whose nth term is 2^n) and (0,2,8,24,64,160,) (whose nth term is n 2^n) are linearly independent. So, to show that they are a basis for the solution space, we just need to check that theyre both solutions.
(T-2I)(T-2I)(2^n) = (T-2I) (T(2^n) 2I 2^n)
= (T-2I) (2^(n+1) 2^(n+1)) = (T-2I)(0) = 0.
(T-2I)(T-2I)(n 2^n) = (T-2I) (T(n 2^n) 2I n 2^n)
= (T-2I) ((n+1) 2^(n+1) n 2^(n+1)) = (T-2I) (2^(n+1))
= 2 (T-2I) (2^n) = 0.
Likewise for any multiple root (the algebra just gets a little messier).
The solutions to (T-rI)^m (f) = 0 form an m-dimensional subspace of sequence space, one basis for which is given by the functions
f_0(n) = r^n, f_1(n) = n r^n, ..., f_{m-1}(n) = n^{m-1} r^n.
E.g., for r=1, the solutions to (T-I)^m (f) form a space with basis
f_0(n) = 1, f_1(n) = n, f_2(n) = n^2, ...,
f_{m-1}(n) = n^{m-1}.
This space is just the space of polynomials of degree < m.
But the following less obvious basis is also frequently useful:
f_0(n) = 1,
f_1(n) = n,
f_2(n) = n(n-1)/2,
f_3(n) = n(n-1)(n-2)/6,
Suppose we know that a sequence is given by a cubic polynomial,
but we dont know its coefficients.
How do we find them?
E.g., the sequence 0, 1, 5, 15, 34, 65, 111, ...
(with initial term indexed as term 0).
Note that if p(n) = an^3 + bn^2 + cn + d,
then p(n+1)-p(n) = a((n+1)^3-n^3)+b((n+1)^2-n^2)+c((n+1)-n)+0
= a polynomial in n of degree 2.
Difference tables:
0 1 5 15 34 65
1 4 10 19 31
3 6 9 12
3 3 3
How can we use the initial numbers 0 1 3 3 to reconstruct
the formula for f(n)?
Look at the difference-tables for the function 1, n, n(n-1)/2, and
n(n-1)(n-2)/6:
1:
1 1 1 1
0 0 0
0
0
n:
0 1 2 3
1 1 1
0
0
n(n-1)/2:
0 0 1 3
0 1 2
1
0
n(n-1)(n-2)/6:
0 0 0 1
0 0 1
1
1
So a cubic polynomial whose difference table has rows that begin
0, 1, 3, 3, ... must equal 0(1)+1(n)+3(n(n-1)/2)+3(n(n-1)(n-2)/6)
=(1)n+(3/2)n^2-(3/2)n+(3/6)n^3-(9/6)n^2+(6/6)n
=(1/2)n^3+(1/2)n=(n^3+n)/2.
Fact: The polynomials 1, t, t(t-1)/2, t(t-1)(t-2)/6, ... form an integral
basis for the set of polynomials p(t) with the property that p(n) is an integer for all integers n.
Explain integral basis.
These functions form the falling factorial basis for the space of polynomials, just as the polynomials 1, t, t^2, t^3, ... form the monomial basis for the space of polynomials.
One often writes (t)_0 = 1, (t)_1 = t, (t)_2 = t(t-1)/2, ...
Whenever you have several natural bases,
change-of-basis formulas come into play.
In the homework, youll be asked to establish
some relationships between two such bases.
A week from today,
well see some very interesting combinatorics arising
from the change-of-basis between
the monomial and falling-factorial bases.
t6 j ->?qr)_| E z { 8
z
->?qr)_| E z { 8
z
Nz
,12b
S
z
Bu>Y)Jhk4W_goRc'Zu"8std
Nz
,12b
S
z
Bu>Y)Jhk4W_goRc'Zu"8st>bw8Zmn>bw8Zmn L\]`amnxy{|~8ztDE.Aw
V L\]`amnxy{|~
&F
@
&F8z
&F
&F
@tDE.Aw/ =!"#$%
[(@(NormalCJ mH ,@, Heading 3$@&00 Heading 4$@&6<A@<Default Paragraph Font*B@* Body Text6(U@( Hyperlink>*B*8V@8FollowedHyperlink>*B*:
%R[ # a j n w
(
2
6
@
B
E
%+,-GHef%
(
jk~anJames Propp*C:\WINDOWS\Desktop\491\Lectures\Sept25.docJames Propp*C:\WINDOWS\Desktop\491\Lectures\Sept25.docJames Propp*C:\WINDOWS\Desktop\491\Lectures\Sept25.docJames Propp*C:\WINDOWS\Desktop\491\Lectures\Sept25.docJames Propp*C:\WINDOWS\Desktop\491\Lectures\Sept25.docJames Propp/C:\WINDOWS\TEMP\AutoRecovery save of Sept25.asdJames Propp/C:\WINDOWS\TEMP\AutoRecovery save of Sept25.asdJames Propp/C:\WINDOWS\TEMP\AutoRecovery save of Sept25.asdJames ProppC:\WINDOWS\Desktop\Sept25.docJames ProppC:\WINDOWS\Desktop\Sept25.docF d}i[K#"x`1fK1 A94v>|h?b<"YB H\ wk$l An X=x hhOJQJo(`o(`o(0o(()hhOJQJo(`o(0o(()0o(()hhOJQJo(hho(()0o(()hho(.hhOJQJo(hhOJQJo(?wkx`1AnK1FX=xH\lv>"YBK#A9d}i@`md`@G:Times New Roman5Symbol3&:Arial;Wingdings"qhGyFLyFGyF/$0d<C:\Program Files\Microsoft Office\Templates\sixteenpoint.dotFormal power seriesJames ProppJames Propp
Oh+'0
8DP
\hpxFormal power seriesormJames Proppamesixteenpoint.dotesJames Propp3meMicrosoft Word 8.0@F#@@@0
՜.+,D՜.+,Php
UW Math Department/jFormal power seriesTitle 6>
_PID_GUIDAN{D6192561-AA77-11D5-A227-C7476C1BAA7B}
!"#$%&')*+,-./1234567:Root Entry F`D(<1Table!WordDocument:SummaryInformation((DocumentSummaryInformation80CompObjjObjectPool
FMicrosoft Word Document
MSWordDocWord.Document.89q