Week 9-10: Recurrence Relations And Generating Functions

We claim that Wk (m 1) 0. It is enough to show that for the same coefficientsc1, c2, . . . , ck above, the linear relationkXcj um k,j c1um k,1 c2ui,2 · · · ck um k,k 0j 1holds. In fact, applying the recurrence relation (5) to (um k,1), (um k,2), . . .,(um k,k ) respectively, we havekXcj um k,j kXj 1j 1 k 1Xcjk 1Xαi(m k)um i,ji 0αi(m k)i 0kXcj um i,j 0.j 1This means that the vectors (um i,1), (um i,2), . . ., (um i,k ), with 1 i k,are linearly dependent. So Wk (m 1) 0. Continue the procedure, we see thatWk (n) 0 for n m.Theorem 2.5. The solutions (un,1), (un,2), . . ., (un,k ) of the homogeneouslinear recurrence relation (5) are linearly independent if and only if there isa nonnegative integer n0 such that the WronskianWk (n0) 6 0.In other words, the solutions (un,1), (un,2), . . ., (un,k ) are linearly dependentif and only if Wk (n) 0 for all n 0.Proof. We show that the sequences (un,1), (un,2), . . ., (un,k ) are linearly dependent if and only if Wk (n) 0 for all n 0. If (un,1), (un,2), . . ., (un,k ) arelinearly dependent, then for n 0 the columns of the matrix un,1un,2···un,k un 1,2 · · · un 1,k un 1,1 . un k 1,1 un k 1,2 · · · un j 1,k11

are linearly dependent because the columns are part of the sequences (un,1),(un,2), . . ., (un,k ) respectively. It follows from linear algebra that the determinantof the matrix is zero, i.e., the Wronskian Wk (n) 0 for all n 0.Conversely, if Wk (n) 0 for all n 0, in particular, Wk (0) 0, then thereare constants c1, c2, . . . , ck , not all zero, such thatkXcj ui,j c1ui,1 c2ui,2 · · · ck ui,k 0,i 0, 1, . . . , k 1.j 1PWe claim that kj 1 cj un,j 0 for all n by induction. Assume it is true forn m 1. Applying the recurrence relation (5) to the sequences (um,1), (um,2),. . ., (um,k ), we havekXcj um,j j 1kXj 1 kXcjkXαi(k)um i,ji 1αi(k)i 1kXcj um i,j 0.j 1This means that the sequences (un,1), (un,2), . . ., (un,k ) are linearly dependent.3 Homogeneous linear recurrence relations with constant coefficientsIn this section we only consider linear recurrence relations of the formxn α1xn 1 α2xn 2 · · · αk xn k ,αk 6 0,n k,(7)where α1, α2, . . ., αk are constants. We call this kinds of recurrence relations ashomogeneous linear recurrence relations of order k with constantcoefficients. Sometimes it is convenient to write (7) as of the formα0xn α1xn 1 · · · αk xn k 0,n k(8)where α0 6 0 and αk 6 0. The following polynomial equationα0tk α1tk 1 · · · αk 1t αk 0,12(9)

is called the characteristic equation associated with the recurrence relation(8), and the polynomial on the left side of (9) is called the characteristicpolynomial.Example 3.1. The Fibonacci sequence (fn; n 0) satisfies the linear recurrence relationfn fn 1 fn 2, n 2of order 2 with α1 α2 1 in (7).Example 3.2. The geometric sequence (xn; n 0), where xn q n, satisfiesthe linear recurrence relationxn qxn 1,n 1of order 1 with α1 q in (7).It is quite heuristic that solutions of the first order homogeneous linear recurrence relations are geometric sequences. This hints that the recurrence relation(7) may have solutions of the form xn q n. The following theorem confirms thespeculation.Theorem 3.1. (a) For any number q 6 0, the geometric sequencexn q nis a solution of the kth order homogeneous linear recurrence relation (8) withconstant coefficients if and only if the number q is a root of the characteristicequation (9).(b) If the characteristic equation (9) has k distinct roots q1, q2, . . ., qk ,then the general solution of (8) isxn c1q1n c2q2n · · · ck qkn,n 0.(10)Proof. (a) Put xn q n into the recurrence relation (8). We obtainα0q n α1q n 1 · · · αk q n k 0.(11)Since q 6 0, dividing both sides of (11) by q n k , we haveα0q k α1q k 1 · · · αk 1q αk 013(12)

This means that (11) and (12) are equivalent. This finishes the proof of Part(a).(b) Since q1, q2, . . . , qk are roots of the characteristic equation (9), xn qin aresolutions of the homogeneous linear recurrence relation (8) for all i (1 i k).Since the solution space of (8) is a vector space, the linear combinationxn c1q1n c2q2n · · · ck qkn,n 0are also solutions (8). Now given arbitrary values for x0, x1, . . . , xk 1, the sequence (xn) is uniquely determined by the recurrence relation (8). Setc1q1i c2q2i · · · ck qki xi,0 i k 1.The coefficients c1, c2, . . . , ck are uniquely determined by Cramer’s rule as follows:det Ai, 1 i kci det Awhere A is the Vandermonde matrix 11 ··· 1 qq2 · · · qk 1 222 A q1q2 · · · q k , . . q1k 1 q2k 1 · · · qkk 1and Ai is the matrix obtained from A by replacing its ith column by the column[x0, x1, . . . , xk 1]T . The determinant of A is given byYdet A (qj qi) 6 0.1 i j kThis finishes the proof of Part (b).Example 3.3. Find the sequence (xn) satisfying the recurrence relationxn 2xn 1 xn 2 2xn 3,n 3and the initial conditions x0 1, x1 2, and x2 0.14

Solution. The characteristic equation of the recurrence relation isx3 2x2 x 2 0.Factorizing the equation, we have(x 2)(x 1)(x 1) 0.There are three roots x 1, 1, 2. By Theorem 3.1, we have the general solutionxn c1( 1)n c2 c32n.Applying the initial conditions, c1 c2 c3 1c c2 2c3 2 1c1 c2 4c3 0Solving the linear system we have c1 2, c2 2/3, c3 1/3. Thus12xn 2 ( 1)n 2n.33Theorem 3.2. (a) Let q be a root with multiplicity m of the characteristicequation (9) associated with the kth order homogeneous linear recurrencerelation (8) with constant coefficients. Then the m sequencesxn q n ,nq n,.,nm 1q nare linearly independent solutions of the recurrence relation (8).(b) Let q1, q2, . . . , qs be distinct nonzero roots with the multiplicitiesm1 ,m2 ,.,msrespectively for the characteristic equation (9). Then the sequencesxn q1n,q2n,.qsn,nq1n,nq2n,.nqsn,.,.,.,nm1 1q1n;nm2 1q2n;.nms 1qsn;n 0are linearly independent solutions of the homogeneous linear recurrence relation (8). Their linear combinations form the general solution of the recurrence relation (8).15

Proof. The falling factorial polynomial of degree i is the polynomial[t]i : t(t 1) · · · (t i 1).Let q be a root of the characteristic polynomialP (t) α0tk α1tk 1 · · · αk 1t αk (t q)mQ(t)with multiplicity m. Then q is a root of the ith derivative P (i)(t) of P (t), where0 i m 1. We claim that xn [n]iq n is a solution of the recurrence relationfor each i 0, 1, . . . , m 1. In fact,LHS of (8) α0[n]iq n α1[n 1]iq n 1 · · · αk [n k]iq n k ¡ n di in 1n k qαt αt ··· αt01kdti t q i ¡ k n ki d k 1 q · i α0t α1t · · · αk 1t αk tdt t q i d q i · i (t q)mR(t), where R(t) Q(t)tn k .dt t qApplying the Leibniz rule,i µ ¶µ j Xid iLHS of (8) qjdtj qij 0i µXj 0ij¶¶µ(t q)mt q [m]j (t q)m j µt q d dti j ¶i jR(t)t q ¶di j R(t) 0.dti j t qSo xn [n]iq n is a solution. Note that[t]i a0 a1t · · · aiti,(i 0, 1, . . . , m 1)for some integers a0, a 1, . . . , ai. It follows that there some integers b0, b1, . . . , bisuch thatti b0[t]0 b1[t]1 · · · bi[t]i,i 0, 1, . . . , m 1.We see thatxn niq n b0[n]0q n b1[n]1q n · · · bi[n]iq n16

is a solution, where 0 i m 1. Next we show that q n, nq n, . . . , nm 1q n arelinearly independent. Setc0q n c1nq n · · · cm 1nm 1q n 0, n 0.Since q 6 0, we havec0 c1n · · · cm 1nm 1 0 n 0.Consider c0, c1, . . . , cm 1 as variables and let n 1, 2, . . . , m. We have a systemof linear equations about c0, c1, . . . , cm 1. The coefficient matrix 2m 11 1 1 ··· 1 1 2 22 · · · 2m 1 A 1 3 32 · · · 3m 1 . . . . . . 1 m m2 · · · mm 1Qand det A 1 i j m(j i) 6 0. Hence c0 c1 · · · cm 1 0.Proof of General Linear Independence of Solutions: Consider the linear combinationsX(13)(cj,1qjn cj,2nqjn · · · cj,mj nmj 1qjn) 0j 1with coefficients cj,1, cj,2, . . . , cj,mj , where j 1, . . . , s. We assume the rootsq1, . . . , qs are already arranged in increasing order of their modulus as q1 q2 · · · qs , and the roots of equal modulus are are already arrangedin increasing order of their multiplicities. Let qr , . . . , qs be all roots of largestmodulus with the same largest multiplicity m mr · · · ms. We may haver 1. Assume r 1. Then q1 · · · qr 1 qr · · · qs .We have either qr 1 qr or qr 1 qr . If qr 1 qr , we must havemr 1 mr . Let ωj qj /qs for j 1, . . . , s. Then ωr , . . . , ωs are distinct rootsof unity. Divide both sides of (13) by nm 1qsn and move the lower order terms17

to the right, we obtainsXcj,mωjn ε(n) 0 (n ).j rLet A(n) be the (s r 1) (s r 1) matrix nωrnωr 1···ωsn n 1n 1ωr 1· · · ωsn 1 ωrA(n) . n s rωrn s r ωr 1· · · ωsn s r , and Aj (n) the matrix obtained from A(n) by replacing its jth column with[ε(n), ε(n 1), . . . , ε(n s r)]T .QnThen det A(n) ωrnωr 1· · · ωsn r i j s(ωj ωi) 6 0. By Cramer’s rule, wehavedet Aj (n) 0 (n ), j r, . . . , s.cj,m det A(n)It follows that cj,m 0 for j r, . . . , s. Likewise, applying the same method toother nonzero coefficients with highest order, we see that all coefficients in (13)are zero. 4 Matric representation of linear recurrence relationsLet us write x0 [x0, x1, . . . , xk 1]T , x1 [xk , xk 1, . . . , x2k 1]T , . . . ,xn [xnk , xnk 1, . . . , xnk k 1]T ,n 0.Assume xm a1xm 1 a2xm 2 · · · ak xm k , m k. We see thatxn Axn 1,n 1.xn A n x 0 ,n 0.ThenExample 4.1. Find the sequence (xn) satisfying the recurrence relationxn 2xn 1 xn 2 2xn 3,n 3and the initial conditions x0 1, x1 2, and x2 0.18

The recurrence relation can be repeated as x3 2x2 x1 2x0 2x0 x1 2x2x 2x3 x2 2x1 4x0 5x2 4x5 2x4 x3 2x2 10x0 x1 10x2Thus x3 2 1 2x0 x4 4 0 5 x1 ,x5 10 1 10x2i.e., x1 Ax0It follows that xn Axn 1 A2xn 2 · · · Anx0. n x3n 2 1 2x0xn x3n 1 4 0 5 x1 ,x3n 2 10 1 10x2n 0.5 Nonhomogeneous linear recurrence relations with constant coefficientsTheorem 5.1. Given a nonhomogeneous linear recurrence relation of thefirst orderxn αxn 1 βn, n 1.(14)(a) Let βn cq n be an exponential function of n. Then (14) has a particularsolution of the following form. If q 6 α, then xn Aq n. If q α, then xn Anq n.P(b) Let βn ki 0 bini be a polynomial function of n with degree k. If α 6 1, then (14) has a particular solution of the formx n A 0 A 1 n A2 n 2 · · · A k n k ,19

where the coefficients A0, A1, . . ., Ak are recursively determined asAk bk,1 α µ¶kX1 jAi bi α( 1)j iAj ,1 αij i 10 i k 1. If α 1, then the solution of (14) is given byxn x0 nXβi.i 1Proof. (a) We may assume q 6 0; otherwise the recurrence (14) is homogeneous.For the case q 6 α, put xn Aq n in (14); we haveAq n αAq n 1 cq n.The coefficient A is determined as A cq/(q α).For the case q α, put xn Anq n in (14); we haveAnq n αA(n 1)q n 1 cq n.Since q α, then αAq n 1 cq n. The coefficient A is determined as A cq/α.Pk(b) For the case α 6 1, put xn j 0 Aj nj in (14); we obtainkXjAj n αj 0ThenkXjAj n αj 0kXjAj (n 1) kXj 0kXj 0Ajbj n j .j 0j µ ¶Xjii 0ij in ( 1) kXbj n j .j 0µ ¶kXjAi n i αni( 1)j iAj bi n i .ii 0i 0j ii 0 µ ¶kkXXj Ai bi α( 1)j iAj ni 0.ij ii 0kXkXkX20

The coefficients A0, A1, . . . , Ak are determined recursively asAk bk,1 α µ ¶j1 bi α( 1)j iAj ,Ai i1 αj i 1kX0 i k 1.As for the case α 1, iterate the recurrence relation (14); we havexn xn 1 βn xn 2 βn 1 βn xn 1 βn 2 βn 1 βn · · · x0 β1 β2 · · · βn.Example 5.1. Solve the difference equation½xn xn 1 3n2 5n3, n 1x0 2.Solution.xn x0 2 3nXbi 2 i 1nXi2 5i 1nX¡23i 5i3 i 1nX3ii 1n(n 1)(2n 1) 5 2 3 6µWe have applied the following identitiesnXi2 i 1nXi 1n(n 1)(2n 1),6µi3 n(n 1)221¶2.n(n 1)2¶2.

Example 5.2. Solve the equation½xn 3xn 1 4n, n 1x0 2.Solution. Note that xn 3nc is the general solution of the correspondinghomogeneous linear recurrence relation. Let xn An B be a particularsolution. ThenAn B 3[A(n 1) B] 4nComparing the coefficients of n0 and n, it follows that A 2 and B 3. Thusthe general solution is given byxn 2n 3 3nc.The initial condition x0 2 implies that c 1. Therefore the solution isxn 3n 2n 3.Theorem 5.2. Given a nonhomogeneous linear recurrence relation of thesecond orderxn α1xn 1 α2xn 2 cq n.(15)Let q1 and q2 be solutions of its characteristic equationx2 α1x α2 0.Then (15) has a particular solution of the following forms, where A is aconstant to be determined.(a) If q 6 q1, q 6 q2, then xn Aq n.(b) If q q1, q1 6 q2, then xn Anq n.(c) If q q1 q2, then xn An2q n.Proof. The homogeneous linear recurrence relation corresponding to (15) isxn α1xn 1 α2xn 2,n 2.We may assume q 6 0. Otherwise (15) is homogeneous.22(16)

(a) Put xn Aq n into (15); we haveAq n α1Aq n 1 α2Aq n 2 cq n.ThenA(q 2 a1q a2) cq 2.Since q is not a root of the characteristic equation x2 α1x α2, that is,q 2 α1q α2 6 0, the coefficient A is determined ascq 2A 2.q α1q α2(b) Since q q1 6 q2, then xn q n is a solution of (16) but xn nq n is not,that is,q 2 α1q α2 0 and nq n 6 α1(n 1)q n 1 α2(n 2)q n 2.It follows thatnq 2 α1(n 1)q α2(n 2) n(q 2 α1q α2) α1q 2α2 α1q 2α2 6 0.Put xn Anq n into (15); we haveAnq n α1A(n 1)q n 1 α2A(n 2)q n 2 cq n.Then A nq 2 α1(n 1)q α2(n 2) cq 2.Since α1q 2α2 6 0, the coefficient A is determined ascq 2A .α1q 2α2(c) Since q q1 q2, then both xn q n and xn nq n are solutions of (16),but xn n2q n is not. It then follows thatq 2 α1q α2 0,α1q 2α2 0,andn2q 2 α1(n 1)2q α2(n 2)2 n2(q 2 α1q α2) 2n(α1q 2α2) α1q α1q 4α2 6 0.23

Put xn An2q n into (15); we have Aq n 2 n2q 2 α1(n 1)2q α2(n 2)2 cq n.The coefficient A is determined ascq 2.A α1q 4α2Example 5.3. Solve the equation xn 10xn 1 25xn 2 5n 1, n 2x 5 0x1 15.Put xn An2 5n into the recurrence relation. We haveAn2 5n 10A(n 1)2 5n 1 25A(n 2)2 5n 2 5n 1.Dividing both sides we further haveAn2 2A(n 1)2 A(n 2)2 5.Thus A 5/2. The general solution is given by5xn n25n c15n c2n5n.2Applying the initial conditions x0 5 and x1 15, we have c1 5 andc2 9/2. Henceµ¶5 2 9xn n n 5 5n.22Theorem 5.3. Given a nonhomogeneous linear recurrence relation of thesecond orderxn α1xn 1 α2xn 2 βn, n 2,(17)where βn is a polynomial function of n with degree k.24

(a) If α1 α2 6 1, then (17) has a particular solution of the formx n A0 A 1 n · · · Ak n k ,where A0, A1, . . ., Ak are constants to be determined. If k 2, then aparticular solution has the formx n A0 A1 n A 2 n 2 .(b) If α1 α2 1, then (17) can be reduced to a first order recurrencerelationyn (α1 1)yn 1 βn, n 2,where yn xn xn 1 for n 1.PkPkjjProof. (a) Let βn bn.Putx nj 0 jj 0 Aj n into the recurrencerelation (17); we obtainkXj 0jAj n α1kXjAj (n 1) α2j 0kXj 0jAj (n 2) kXbj n jj 0µ ¶j α1Aj( 1)j iniij 0i 0µ ¶jkkXXXij i j α2n Aj( 2)bj n jij 0i 0j 0µ ¶kkXXj α1ni( 1)j iAjii 0j iµ ¶kkkXXXj α2ni( 2)j ibj n j .Aj ii 0j ij 0kXjXCollecting the coefficients of ni, we have µµ¶¶kkkkXXXXjjj ij i Ai α1( 1)( 2)bi ni 0.Aj α2Aj iij ij ii 0i 025

Since α1 α2 6 1, the coefficients A0, A1, . . ., Ak are determined asAk bk,1 α1 α2 µ ¶³ 1jj ij i bi Ai ( 1)α1 2 α2 Aj ,1 α1 α2ij i 1kXwhere 0 i k 1.(b) The recurrence relation (17) becomesxn α1xn 1 (1 α1)xn 2 βn,n 2.Set yn xn xn 1 for n 1; the recurrence (17) reduces to a first orderrecurrence relation.Example 5.4. Solve the xnx 0x1following recurrence relation 6xn 1 9xn 2 8n2 24n 5 5.Solution. Put xn A0 A1n A2n2 into the recurrence relation; we obtainA0 A1n A2n2 6[A0 A1(n 1) A2(n 1)2] 9[A0 A1(n 2) A2(n 2)2] 8n2 Collecting the coefficients of n2, n, and the constant, we have(4A2 8)n2 (4A1 24A2 24)n (4A0 12A1 30A2) 0.We conclude that A2 2, A1 6, and A0 3. So xn 2n2 6n 3 is aparticular solution. Then the general solution of the recurrence isxn 2n2 6n 3 3nc1 3nnc2.Applying the initial condition x0 x1 5, we have c1 2, c2 4. Thesequence is finally obtained asxn 2n2 6n 3 2 3n 4n 3n.26

6 Generating functionsThe (ordinary) generating function of an infinite sequencea0 , a 1 , a 2 , . . . , a n , . . .is the infinite seriesA(x) a0 a1x a2x2 · · · anxn · · · .A finite sequencea0 , a 1 , a 2 , . . . , a ncan be regarded as the infinite sequencea0, a1, a2, . . . , an, 0, 0, . . .and its generating functionA(x) a0 a1x a2x2 · · · anxnis a polynomial.Example 6.1. The generating function of the constant infinite sequence1, 1, . . . , 1, . . .is the functionA(x) 1 x x2 · · · xn · · · 1.1 xExample 6.2. For any positive integer n, the generating function for the binomial coefficients³n ³n ³n ³n ,,, .,, 0, . . .012nis the functionn ³ Xn kx (1 x)n.kk 027

Example 6.3. For any real number α, the generating function for the infinitesequence of binomial coefficients³α ³α ³α ³α ,,, .,, .012nis the function ³ Xα nx (1 x)α .nn 0Example 6.4. Let k be a positive integer and leta0 , a 1 , a 2 , . . . , a n , . . .be the infinite sequence whose general term an is the number of nonnegativeintegral solutions

Example 1.4. The Fibonacci number fn is even if and only if n is a multiple of 3. Note that f1 f2 1 is odd and f3 2 is even. Assume that f3k is even, f3k¡2 and f3k¡1 are odd. Then f3k 1 f3k f3k¡1 is odd (even odd odd), and subsequently, f3k 2 f3k 1 f3k is also odd (odd even odd).It follows that f3(k 1) f3k 2 f3k 1 is ev