18 312 Algebraic Combinatorics Lionel Levine Lecture 6 Lecture date Feb 17 2011 1 Reprise of d dx Notes by Dennis Tseng ln E Let E denote the shift operator such that for a sequence of numbers s0 s1 s2 E s0 s1 s2 s1 s2 s3 In the previous lecture we mentioned the equation d E e dx Also as mentioned in the last lecture we can also have E operate on functions If f is a function then let Ef x f x 1 We can also define E h to be E h f x f x h where h is any real number d To better understand the equation E d dx we recall the Taylor expansion of ex et 1 t t2 tn 2 n d In a similar way we can think of et dx as d 2 d n t2 dx tn dx d e 1 t 1 dx 2 n In 1 above multiplication of operators is the same as the composition of operators In td d n dn particular dx dx n Now given the definition 1 we can let e dt operate on a function h di t2 tn et dx f f tf 0 f 00 f n 2 n Now if we plug in x 0 we get d t dx f 0 tf 0 0 t2 00 2 f 0 tn n 0 n f h di which is the Taylor series for f t so we can write et dx at x 0 as f t We can also write where E t f 0 f t Therefore E t f 0 f t hf t d byi using the shift operator d d et dx f 0 and E t et dx When we plug t 1 as get E e dx as desired 6 1 1 1 Eigenvectors and eigenvalues of E If we look at how E operators on sequences if the sequence s0 s1 s2 is an eigenvector of E with eigenvalue then E s0 s1 s2 s0 s1 s2 s1 s2 s3 s0 s1 s2 Therefore sn 1 sn for all n 0 and sn s0 n for all nonnegative integer n and nonzero s0 Also using methods learned in a differential equations class we can show that the eigend vectors of dx with eigenvalue are functions in the form f x ce x for some constant c 6 0 These eigenvectors are essentially the same thing as sn s0 n s0 e n where ln d Therefore if s is the sequence s0 s1 Es s e s and dx f f d have the same eigenvectors ce x but different eigenvalues We see The operators E and dx d that ce x has eigenvalue for dx and eigenvalue e for E 2 Linear Recurrence Sequences From previous lectures we have shown that the following conditions for sequences that satisfy linear recurrences are equivalent We say that sn n 0 satisfies a linear recurrence of order k if any of the follow is true 1 There exists constants a0 ak 1 C such that sn k k 1 X ai sn i i 0 for all n 0 An example of this is sn 3 2sn 2 5sn 1 sn 2 The terms of the sequences can be expressed as sn m X qi n ni i 1 where 1 m are constants in C q1 x q2 x qm x are polynomials over the m X complex numbers in C x and deg qi k i 1 6 2 3 The exponential generating function F x X sn n 0 xn n satisfies a linear differential equation of order k This is true because you shift the series when you differentiate We will present a couple more equivalent conditions 4 The ordinary generating function Fs x X sn xn n 0 is P x Q x for some polynomials P x Q x C x such that deg P deg Q k 5 We can express the terms of the sequence as sn v t An w for some k by k matrix A aij ki j 1 and some vectors v and w 2 1 Proof of condition 4 We will prove the fourth condition is equivalent to the first condition If Fs x where Q x k X ai xi we get i 0 P x Q x Q x Fs x P x k X X ai xi sn xn P x Fs x i 0 n 0 After expanding we get X X m 0 i n m ai sn 6 3 xm P x P x Q x Now equate coefficients of xm If m k then the coefficient of xk on the right side is 0 since P x must have degree less than k So if m k X ai sn 0 i n m k X ai sm i 0 2 i 0 P x Q x The equation 2 is a linear recurrence of order k In the equation Fs x Q x encodes the coefficients of the recurrence and P x encodes the initial conditions 2 2 Proof of condition 5 We will prove fifth condition also defines a sequence that satisfies a linear recurrence of order k To do this we will use the Cayley Hamilton Theorem Theorem 1 Let A be a square matrix If A x det xI A is the characteristic polynomial of A then A A 0 To show that the fifth definition also defines a sequence that satisfies a linear recurrence of order k we first show that if the nth term of the sequence can be expressed as v t An w for a k X k by k matrix A and vectors v and w Let the characteristic polynomial A x be ci xi i 0 Then for any nonnegative integer n k X i 0 ci sn i k X ci v t An i w i 0 k X vt ci An i w i 0 v t A n k X ci A i w i 0 v t An A A w v t An 0 w 0 One direction is proven How we need to show that we can represent any linear recurrence in this form 6 4 Given Sn satisfying a linear recurrence k X ci sn i 0 i 0 for all nonnegative integer n and ck 1 we want to find a matrix A such that its characteristic polynomial is k X A x ci xi i 0 One method is to factor A into k Y x i where i are the roots of A with multiplicity i 1 Then let 1 0 0 2 A 0 0 We could also create an integer matrix if matrix 0 1 0 0 A 0 0 c0 c1 0 0 k ci are integers for all 0 i k Let A be the 0 0 0 0 1 0 ck 2 ck 1 where A has 1 s on the superdiagonal 1 times the coefficients of A in the last row and 0 s …