Ch.3: Solving Recursions

From the lecture notes "Combinatorics, Graphs, Matroids" (University of Bonn, winter term 2025/26) 3.1. Linear Recursions of Depth 1 3.2. Generating Functions 3.3. Using Generating Functions to Solve Recursions 3.4. Exponential Generating Functions

82 flashcards · Mathematics · by lakesare

Part of University of Bonn › V3C2: Combinatorics, Graphs, Matroids · 6 courses

[Linear Recursions of Depth 1] A sequence is given by T0=βT_0 = \betaT0=β and Tn=anTn−1+bnT_n = a_n T_{n-1} + b_nTn=anTn−1+bn for n≥1n \ge 1n≥1 , where all an≠0a_n \ne 0an=0 . What is the closed formula for TnT_nTn ?
Tn=∏k=1nak(∑k=1nbk∏i=1kai+T0)\displaystyle\boldsymbol{T_n = \prod_{k=1}^{n} a_k \left( \sum_{k=1}^{n} \frac{b_k}{\prod_{i=1}^{k} a_i} + T_0 \right)}Tn=k=1∏nak(k=1∑n∏i=1kaibk+T0) Sanity check with all bk=0b_k = 0bk=0 : Tn=a1a2⋯an T0T_n = a_1 a_2 \cdots a_n \, T_0Tn=a1a2⋯anT0 .
[Linear Recursions of Depth 1] If T0=βT_0 = \betaT0=β and Tn=anTn−1+bnT_n = a_n T_{n-1} + b_nTn=anTn−1+bn ( n≥1n \ge 1n≥1 ) with all an≠0a_n \ne 0an=0 , then Tn=∏k=1nak(∑k=1nbk∏i=1kai+T0)\displaystyle T_n = \prod_{k=1}^{n} a_k \left( \sum_{k=1}^{n} \frac{b_k}{\prod_{i=1}^{k} a_i} + T_0 \right)Tn=k=1∏nak(k=1∑n∏i=1kaibk+T0) .How is this proved?
Induction on nnn : plug the formula for Tn−1T_{n-1}Tn−1 into Tn=anTn−1+bnT_n = a_n T_{n-1} + b_nTn=anTn−1+bn . The factor ana_nan turns ∏k=1n−1ak\prod_{k=1}^{n-1} a_k∏k=1n−1ak into ∏k=1nak\prod_{k=1}^{n} a_k∏k=1nak , and bn=∏k=1nak⋅bn∏i=1naib_n = \prod_{k=1}^{n} a_k \cdot \frac{b_n}{\prod_{i=1}^{n} a_i}bn=∏k=1nak⋅∏i=1naibn is exactly the new summand k=nk = nk=n .
[Linear Recursions of Depth 1] In the recursion Tn=anTn−1+bnT_n = a_n T_{n-1} + b_nTn=anTn−1+bn , what does the word inhomogeneous refer to?
The additive terms bnb_nbn may be non-zero. Tn=anTn−1+bnT_n = a_n T_{n-1} + b_nTn=anTn−1+bn is a linear inhomogeneous recursion of depth 1 ( TnT_nTn depends only on Tn−1T_{n-1}Tn−1 ).
[Linear Recursions of Depth 1] T0=βT_0 = \betaT0=β and Tn=aTn−1+bT_n = a T_{n-1} + bTn=aTn−1+b for n≥1n \ge 1n≥1 , with constants a≠1a \ne 1a=1 and bbb . Tn= ?T_n = \; ?Tn=?
Tn=anT0+b an−1a−1\displaystyle\boldsymbol{T_n = a^n T_0 + b \, \frac{a^n - 1}{a - 1}}Tn=anT0+ba−1an−1 For a=1a = 1a=1 the fraction is undefined; then simply Tn=T0+nbT_n = T_0 + nbTn=T0+nb .
[Linear Recursions of Depth 1] T0=βT_0 = \betaT0=β , Tn=aTn−1+bT_n = a T_{n-1} + bTn=aTn−1+b ( n≥1n \ge 1n≥1 , a≠1a \ne 1a=1 ) gives Tn=anT0+ban−1a−1T_n = a^n T_0 + b \frac{a^n - 1}{a - 1}Tn=anT0+ba−1an−1 .For a≠0a \ne 0a=0 , how does this follow from the general formula for Tn=anTn−1+bnT_n = a_n T_{n-1} + b_nTn=anTn−1+bn ?
Set all ak=aa_k = aak=a , bk=bb_k = bbk=b , and sum the geometric series ∑k=1n1ak\displaystyle\sum_{k=1}^{n} \frac{1}{a^k}k=1∑nak1 . The general formula gives Tn=an(b∑k=1na−k+T0)T_n = a^n \left( b \sum_{k=1}^{n} a^{-k} + T_0 \right)Tn=an(b∑k=1na−k+T0) , and ∑k=1na−k=1−a−na−1\displaystyle\sum_{k=1}^{n} a^{-k} = \frac{1 - a^{-n}}{a - 1}k=1∑na−k=a−11−a−n , so anb∑k=1na−k=ban−1a−1a^n b \sum_{k=1}^{n} a^{-k} = b \frac{a^n - 1}{a - 1}anb∑k=1na−k=ba−1an−1 .
[Linear Recursions of Depth 1] T0=βT_0 = \betaT0=β , Tn=aTn−1+bT_n = a T_{n-1} + bTn=aTn−1+b ( n≥1n \ge 1n≥1 , a≠1a \ne 1a=1 ) gives Tn=anT0+ban−1a−1T_n = a^n T_0 + b \frac{a^n - 1}{a - 1}Tn=anT0+ba−1an−1 .Why does the case a=0a = 0a=0 need a separate argument, and why does the formula still hold there?
The general formula needs all ak≠0a_k \ne 0ak=0 (it divides by ∏ai\prod a_i∏ai ). For a=0a = 0a=0 directly: Tn=bT_n = bTn=b for n≥1n \ge 1n≥1 , and the formula gives 0+b⋅−1−1=b0 + b \cdot \frac{-1}{-1} = b0+b⋅−1−1=b . For n=0n = 0n=0 the formula gives a0T0+0=T0a^0 T_0 + 0 = T_0a0T0+0=T0 .
[Linear Recursions of Depth 1] Solve T0=0T_0 = 0T0=0 , Tn=2Tn−1+1T_n = 2T_{n-1} + 1Tn=2Tn−1+1 ( n≥1n \ge 1n≥1 ).
Tn=2n−1\boldsymbol{T_n = 2^n - 1}Tn=2n−1 From Tn=anT0+ban−1a−1T_n = a^n T_0 + b \frac{a^n - 1}{a - 1}Tn=anT0+ba−1an−1 with a=2a = 2a=2 , b=1b = 1b=1 , T0=0T_0 = 0T0=0 . Check: 0,1,3,7,150, 1, 3, 7, 150,1,3,7,15 .
[Linear Recursions of Depth 1] DnD_nDn is the number of derangements of {1,…,n}\{1, \dots, n\}{1,…,n} (permutations without fixed points), with D0=1D_0 = 1D0=1 . Which recursion of depth 2 do the DnD_nDn satisfy for n≥2n \ge 2n≥2 ?
Dn=(n−1)(Dn−1+Dn−2)\boldsymbol{D_n = (n-1)(D_{n-1} + D_{n-2})}Dn=(n−1)(Dn−1+Dn−2) Split the derangements by whether 1 lies in a cycle of length 2 or in a cycle of length at least 3.
[Linear Recursions of Depth 1] DnD_nDn is the number of derangements of {1,…,n}\{1, \dots, n\}{1,…,n} (permutations without fixed points), with D0=1D_0 = 1D0=1 .Why are there exactly (n−1)Dn−2(n-1) D_{n-2}(n−1)Dn−2 derangements of {1,…,n}\{1, \dots, n\}{1,…,n} in which 1 lies in a cycle of length 2?
Choose the partner jjj of 1 ( n−1n - 1n−1 ways), then derange the other n−2n - 2n−2 elements ( Dn−2D_{n-2}Dn−2 ways).
[Linear Recursions of Depth 1] DnD_nDn is the number of derangements of {1,…,n}\{1, \dots, n\}{1,…,n} (permutations without fixed points), with D0=1D_0 = 1D0=1 .Why are there exactly (n−1)Dn−1(n-1) D_{n-1}(n−1)Dn−1 derangements of {1,…,n}\{1, \dots, n\}{1,…,n} in which 1 lies in a cycle of length at least 3?
Deleting 1 from its cycle gives a derangement of {2,…,n}\{2, \dots, n\}{2,…,n} , and 1 can be put back after any of its n−1n - 1n−1 elements. Since the cycle of 1 has length at least 3, deleting 1 leaves a cycle of length at least 2, so no fixed point appears.
[Linear Recursions of Depth 1] DnD_nDn is the number of derangements of {1,…,n}\{1, \dots, n\}{1,…,n} (permutations without fixed points), with D0=1D_0 = 1D0=1 . For n≥2n \ge 2n≥2 : Dn=(n−1)(Dn−1+Dn−2)D_n = (n-1)(D_{n-1} + D_{n-2})Dn=(n−1)(Dn−1+Dn−2) .How does this give a recursion of depth 1 for DnD_nDn ?
Dn−nDn−1=−(Dn−1−(n−1)Dn−2)D_n - nD_{n-1} = -(D_{n-1} - (n-1)D_{n-2})Dn−nDn−1=−(Dn−1−(n−1)Dn−2) , so iterating down to n=1n = 1n=1 gives Dn=nDn−1+(−1)n\boldsymbol{D_n = nD_{n-1} + (-1)^n}Dn=nDn−1+(−1)n . Dn−nDn−1=(−1)n−1(D1−D0)=(−1)n−1(0−1)=(−1)nD_n - nD_{n-1} = (-1)^{n-1}(D_1 - D_0) = (-1)^{n-1}(0 - 1) = (-1)^nDn−nDn−1=(−1)n−1(D1−D0)=(−1)n−1(0−1)=(−1)n for n≥1n \ge 1n≥1 .
[Linear Recursions of Depth 1] If T0=βT_0 = \betaT0=β and Tn=anTn−1+bnT_n = a_n T_{n-1} + b_nTn=anTn−1+bn ( n≥1n \ge 1n≥1 ) with all an≠0a_n \ne 0an=0 , then Tn=∏k=1nak(∑k=1nbk∏i=1kai+T0)\displaystyle T_n = \prod_{k=1}^{n} a_k \left( \sum_{k=1}^{n} \frac{b_k}{\prod_{i=1}^{k} a_i} + T_0 \right)Tn=k=1∏nak(k=1∑n∏i=1kaibk+T0) .What does this give for the derangement numbers, using D0=1D_0 = 1D0=1 and Dn=nDn−1+(−1)nD_n = nD_{n-1} + (-1)^nDn=nDn−1+(−1)n ?
Dn=n!∑k=0n(−1)kk!\displaystyle\boldsymbol{D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}}Dn=n!k=0∑nk!(−1)k With ak=ka_k = kak=k , bk=(−1)kb_k = (-1)^kbk=(−1)k : ∏i=1kai=k!\prod_{i=1}^{k} a_i = k!∏i=1kai=k! , so Dn=n!(∑k=1n(−1)kk!+1)D_n = n! \left( \sum_{k=1}^{n} \frac{(-1)^k}{k!} + 1 \right)Dn=n!(∑k=1nk!(−1)k+1) , and the 111 is the summand k=0k = 0k=0 .
[Linear Recursions of Depth 1] DnD_nDn is the number of derangements of {1,…,n}\{1, \dots, n\}{1,…,n} (permutations without fixed points), with D0=1D_0 = 1D0=1 .Compute D1,…,D4D_1, \dots, D_4D1,…,D4 with Dn=nDn−1+(−1)nD_n = nD_{n-1} + (-1)^nDn=nDn−1+(−1)n .
D1=0, D2=1, D3=2, D4=9\boldsymbol{D_1 = 0, \ D_2 = 1, \ D_3 = 2, \ D_4 = 9}D1=0, D2=1, D3=2, D4=9 D1=1⋅1−1D_1 = 1 \cdot 1 - 1D1=1⋅1−1 , D2=2⋅0+1D_2 = 2 \cdot 0 + 1D2=2⋅0+1 , D3=3⋅1−1D_3 = 3 \cdot 1 - 1D3=3⋅1−1 , D4=4⋅2+1D_4 = 4 \cdot 2 + 1D4=4⋅2+1 .
[Generating Functions] What is the generating function of a sequence (an)n∈N(a_n)_{n \in \mathbb{N}}(an)n∈N ?
The formal expression ∑n≥0anzn\displaystyle\boldsymbol{\sum_{n \ge 0} a_n z^n}n≥0∑anzn . Formal: it is a power series in the variable zzz , manipulated coefficientwise; convergence is not part of the definition.
[Generating Functions] How are the sum ∑n≥0anzn+∑n≥0bnzn\sum_{n \ge 0} a_n z^n + \sum_{n \ge 0} b_n z^n∑n≥0anzn+∑n≥0bnzn and the multiple c∑n≥0anznc \sum_{n \ge 0} a_n z^nc∑n≥0anzn ( c∈Rc \in \mathbb{R}c∈R ) of generating functions defined?
Coefficientwise: ∑n≥0(an+bn)zn\displaystyle\sum_{n \ge 0} (a_n + b_n) z^nn≥0∑(an+bn)zn and ∑n≥0(can)zn\displaystyle\sum_{n \ge 0} (c a_n) z^nn≥0∑(can)zn .
[Generating Functions] What is the product of two generating functions? (∑n≥0anzn)(∑n≥0bnzn)= ?\displaystyle\left( \sum_{n \ge 0} a_n z^n \right) \left( \sum_{n \ge 0} b_n z^n \right) = \; ?(n≥0∑anzn)(n≥0∑bnzn)=?
∑n≥0(∑k=0nakbn−k)zn\displaystyle\boldsymbol{\sum_{n \ge 0} \left( \sum_{k=0}^{n} a_k b_{n-k} \right) z^n}n≥0∑(k=0∑nakbn−k)zn The coefficient of znz^nzn collects all products akzk⋅bn−kzn−ka_k z^k \cdot b_{n-k} z^{n-k}akzk⋅bn−kzn−k .
[Generating Functions] The coefficient sequence cn=∑k=0nakbn−kc_n = \sum_{k=0}^{n} a_k b_{n-k}cn=∑k=0nakbn−k of a product of generating functions is called the convolution of (an)(a_n)(an) and (bn)(b_n)(bn) .
[Generating Functions] Which generating functions are the additive identity and the multiplicative identity?
000 (all an=0a_n = 0an=0 ) and 111 ( a0=1a_0 = 1a0=1 , all other an=0a_n = 0an=0 ).
[Generating Functions] When is ∑n≥0bnzn\sum_{n \ge 0} b_n z^n∑n≥0bnzn the (multiplicative) inverse of ∑n≥0anzn\sum_{n \ge 0} a_n z^n∑n≥0anzn ?
When (∑n≥0anzn)(∑n≥0bnzn)=1\displaystyle\boldsymbol{\left( \sum_{n \ge 0} a_n z^n \right) \left( \sum_{n \ge 0} b_n z^n \right) = 1}⎝⎛n≥0∑anzn⎠⎞⎝⎛n≥0∑bnzn⎠⎞=1 .
[Generating Functions] When does a generating function ∑n≥0anzn\sum_{n \ge 0} a_n z^n∑n≥0anzn have an inverse?
If and only if a0≠0a_0 \ne 0a0=0 .
[Generating Functions] Why can't ∑n≥0anzn\sum_{n \ge 0} a_n z^n∑n≥0anzn have an inverse when a0=0a_0 = 0a0=0 ?
The coefficient of z0z^0z0 in the product with any ∑n≥0bnzn\sum_{n \ge 0} b_n z^n∑n≥0bnzn is a0b0=0≠1a_0 b_0 = 0 \ne 1a0b0=0=1 .
[Generating Functions] a0≠0a_0 \ne 0a0=0 . How does one construct the inverse ∑n≥0bnzn\sum_{n \ge 0} b_n z^n∑n≥0bnzn of ∑n≥0anzn\sum_{n \ge 0} a_n z^n∑n≥0anzn ?
Recursively: b0=1a0,bn=−1a0∑k=1nakbn−k\displaystyle\boldsymbol{b_0 = \frac{1}{a_0}, \quad b_n = -\frac{1}{a_0} \sum_{k=1}^{n} a_k b_{n-k}}b0=a01,bn=−a01k=1∑nakbn−k for n≥1n \ge 1n≥1 . Then the coefficient of znz^nzn in the product is ∑k=0nakbn−k=a0bn+∑k=1nakbn−k\sum_{k=0}^{n} a_k b_{n-k} = a_0 b_n + \sum_{k=1}^{n} a_k b_{n-k}∑k=0nakbn−k=a0bn+∑k=1nakbn−k , which is 111 for n=0n = 0n=0 and 000 for n≥1n \ge 1n≥1 .
[Generating Functions] Which of 1−z1 - z1−z , z\ z z , 2+z3\ 2 + z^3 2+z3 have an inverse as generating functions? What is the inverse of 1−z1 - z1−z ?
1−z1 - z1−z and 2+z32 + z^32+z3 do, zzz doesn't (its constant coefficient is 0). (1−z)−1=∑n≥0zn\displaystyle\boldsymbol{(1-z)^{-1} = \sum_{n \ge 0} z^n}(1−z)−1=n≥0∑zn . For 1−z1 - z1−z the recursion is b0=1b_0 = 1b0=1 , bn=−(−1)bn−1=bn−1b_n = -(-1) b_{n-1} = b_{n-1}bn=−(−1)bn−1=bn−1 .
[Generating Functions] Generating functions are formal, yet the course writes identities like ∑n≥0zn=11−z\sum_{n \ge 0} z^n = \frac{1}{1-z}∑n≥0zn=1−z1 . What justifies treating them as functions of zzz ?
In all applications ∣an∣≤Mn|a_n| \le M^n∣an∣≤Mn for some constant M>0M > 0M>0 , so the series converges for ∣z∣<1M|z| < \frac{1}{M}∣z∣<M1 ; zzz is always assumed small enough. The radius of convergence itself is never of interest.
[Generating Functions] ∑n≥0zn= ?\displaystyle\sum_{n \ge 0} z^n = \; ?n≥0∑zn=?
11−z\displaystyle\boldsymbol{\frac{1}{1-z}}1−z1 The geometric series.
[Generating Functions] ∑n≥0anzn= ?\displaystyle\sum_{n \ge 0} a^n z^n = \; ?n≥0∑anzn=? (for a constant a≠0a \ne 0a=0 )
11−az\displaystyle\boldsymbol{\frac{1}{1-az}}1−az1 The geometric series in azazaz .
[Generating Functions] Which function is the generating function of 1,0,1,0,1,0,…1, 0, 1, 0, 1, 0, \dots1,0,1,0,1,0,… ?
11−z2=∑n≥0z2n\displaystyle\boldsymbol{\frac{1}{1-z^2}} = \sum_{n \ge 0} z^{2n}1−z21=n≥0∑z2n The geometric series in z2z^2z2 .
[Generating Functions] m∈Nm \in \mathbb{N}m∈N . ∑n≥0(mn)zn= ?\displaystyle\sum_{n \ge 0} \binom{m}{n} z^n = \; ?n≥0∑(nm)zn=?
(1+z)m\boldsymbol{(1+z)^m}(1+z)m The binomial theorem. The sum is finite, since (mn)=0\binom{m}{n} = 0(nm)=0 for n>mn > mn>m .
[Generating Functions] 1(1−z)2=∑n≥0 ? zn\displaystyle\frac{1}{(1-z)^2} = \sum_{n \ge 0} \; ? \; z^n(1−z)21=n≥0∑?zn , and why?
∑n≥0(n+1)zn\displaystyle\boldsymbol{\sum_{n \ge 0} (n+1) z^n}n≥0∑(n+1)zn 1(1−z)2=(∑n≥0zn)2\frac{1}{(1-z)^2} = \left( \sum_{n \ge 0} z^n \right)^2(1−z)21=(∑n≥0zn)2 , and the convolution of 1,1,1,…1, 1, 1, \dots1,1,1,… with itself has coefficients ∑k=0n1⋅1=n+1\sum_{k=0}^{n} 1 \cdot 1 = n + 1∑k=0n1⋅1=n+1 .
[Generating Functions] ∑n≥0nzn= ?\displaystyle\sum_{n \ge 0} n z^n = \; ?n≥0∑nzn=?
z(1−z)2\displaystyle\boldsymbol{\frac{z}{(1-z)^2}}(1−z)2z 1(1−z)2=∑n≥0(n+1)zn=∑n≥1nzn−1\frac{1}{(1-z)^2} = \sum_{n \ge 0} (n+1) z^n = \sum_{n \ge 1} n z^{n-1}(1−z)21=∑n≥0(n+1)zn=∑n≥1nzn−1 ; multiply by zzz .
[Generating Functions] Which sequence has the generating function 1(1−2z)2\displaystyle\frac{1}{(1-2z)^2}(1−2z)21 ?
an=(n+1) 2n\boldsymbol{a_n = (n+1) \, 2^n}an=(n+1)2n In general ∑n≥0(n+1)cnzn=1(1−cz)2\displaystyle\sum_{n \ge 0} (n+1) c^n z^n = \frac{1}{(1-cz)^2}n≥0∑(n+1)cnzn=(1−cz)21 : substitute czczcz for zzz in 1(1−z)2=∑n≥0(n+1)zn\frac{1}{(1-z)^2} = \sum_{n \ge 0} (n+1) z^n(1−z)21=∑n≥0(n+1)zn .
[Generating Functions] m≥1m \ge 1m≥1 . (11−z)m=∑n≥0 ? zn\displaystyle\left( \frac{1}{1-z} \right)^m = \sum_{n \ge 0} \; ? \; z^n(1−z1)m=n≥0∑?zn
∑n≥0(m+n−1n)zn\displaystyle\boldsymbol{\sum_{n \ge 0} \binom{m+n-1}{n} z^n}n≥0∑(nm+n−1)zn
[Generating Functions] (11−z)m=(∑n≥0zn)m=∑n≥0(m+n−1n)zn\displaystyle\left( \frac{1}{1-z} \right)^m = \left( \sum_{n \ge 0} z^n \right)^m = \sum_{n \ge 0} \binom{m+n-1}{n} z^n(1−z1)m=(n≥0∑zn)m=n≥0∑(nm+n−1)zn Why is the coefficient of znz^nzn equal to (m+n−1n)\binom{m+n-1}{n}(nm+n−1) ?
It counts the ways to choose nnn indistinguishable objects from mmm distinguishable bins. A term zn1⋯znmz^{n_1} \cdots z^{n_m}zn1⋯znm of the product with n1+⋯+nm=nn_1 + \dots + n_m = nn1+⋯+nm=n corresponds to putting nin_ini objects into bin iii .
[Generating Functions] What is the coefficient of z3z^3z3 in 1(1−z)3\displaystyle\frac{1}{(1-z)^3}(1−z)31 ?
10\boldsymbol{10}10 (m+n−1n)\binom{m+n-1}{n}(nm+n−1) with m=3m = 3m=3 , n=3n = 3n=3 : (53)=10\binom{5}{3} = 10(35)=10 .
[Using Generating Functions to Solve Recursions] How are the Fibonacci numbers (Fn)n∈N(F_n)_{n \in \mathbb{N}}(Fn)n∈N defined?
F0=0, F1=1, Fn=Fn−1+Fn−2\boldsymbol{F_0 = 0, \ F_1 = 1, \ F_n = F_{n-1} + F_{n-2}}F0=0, F1=1, Fn=Fn−1+Fn−2 for n≥2n \ge 2n≥2 . 0,1,1,2,3,5,8,13,…0, 1, 1, 2, 3, 5, 8, 13, \dots0,1,1,2,3,5,8,13,…
[Using Generating Functions to Solve Recursions] When is a linear recursion called homogeneous?
When each term is just a weighted sum of previous terms, without any additive term. e.g. Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}Fn=Fn−1+Fn−2 is homogeneous; Dn=nDn−1+(−1)nD_n = nD_{n-1} + (-1)^nDn=nDn−1+(−1)n is not.
[Using Generating Functions to Solve Recursions] What is a homogeneous linear recursion of length kkk ?
an=c1an−1+⋯+ckan−ka_n = c_1 a_{n-1} + \dots + c_k a_{n-k}an=c1an−1+⋯+ckan−k for n≥kn \ge kn≥k , with constants c1,…,ckc_1, \dots, c_kc1,…,ck and given values a0,…,ak−1a_0, \dots, a_{k-1}a0,…,ak−1 . Fibonacci: k=2k = 2k=2 , c1=c2=1c_1 = c_2 = 1c1=c2=1 .
[Using Generating Functions to Solve Recursions] Which 2×22 \times 22×2 matrix MMM satisfies (FnFn−1)=M(Fn−1Fn−2)\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = M \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix}(FnFn−1)=M(Fn−1Fn−2) for the Fibonacci numbers FnF_nFn ?
M=(1110)\boldsymbol{M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}}M=(1110) Hence (FnFn−1)=Mn−1(F1F0)\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = M^{n-1} \begin{pmatrix} F_1 \\ F_0 \end{pmatrix}(FnFn−1)=Mn−1(F1F0) for n≥2n \ge 2n≥2 .
[Using Generating Functions to Solve Recursions] Without a closed formula, how many arithmetic operations suffice to compute the Fibonacci number FnF_nFn from the recursion Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}Fn=Fn−1+Fn−2 ?
O(log⁡n)O(\log n)O(logn) , instead of the Θ(n)\Theta(n)Θ(n) of applying the recursion nnn times. Compute the power Mn−1M^{n-1}Mn−1 of M=(1110)M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}M=(1110) , since (FnFn−1)=Mn−1(F1F0)\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = M^{n-1} \begin{pmatrix} F_1 \\ F_0 \end{pmatrix}(FnFn−1)=Mn−1(F1F0) .
[Using Generating Functions to Solve Recursions] How is a matrix power Mn−1M^{n-1}Mn−1 computed with O(log⁡n)O(\log n)O(logn) arithmetic operations?
Repeated squaring: compute M2kM^{2^k}M2k for k=1,…,⌊log⁡2(n−1)⌋k = 1, \dots, \lfloor \log_2(n-1) \rfloork=1,…,⌊log2(n−1)⌋ , then multiply those M2kiM^{2^{k_i}}M2ki with n−1=2k1+⋯+2ktn - 1 = 2^{k_1} + \dots + 2^{k_t}n−1=2k1+⋯+2kt (binary representation). Each M2k=(M2k−1)2M^{2^k} = (M^{2^{k-1}})^2M2k=(M2k−1)2 costs a constant number of operations (for a matrix of fixed size), and there are O(log⁡n)O(\log n)O(logn) of them.
[Using Generating Functions to Solve Recursions] Computing the Fibonacci number FnF_nFn via powers of (1110)\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}(1110) takes O(log⁡n)O(\log n)O(logn) arithmetic operations. Does this trick work for other recursions?
Yes, for every homogeneous linear recursion of length kkk , an=c1an−1+⋯+ckan−ka_n = c_1 a_{n-1} + \dots + c_k a_{n-k}an=c1an−1+⋯+ckan−k . Use a k×kk \times kk×k matrix that maps (an−1,…,an−k)(a_{n-1}, \dots, a_{n-k})(an−1,…,an−k) to (an,…,an−k+1)(a_n, \dots, a_{n-k+1})(an,…,an−k+1) .
[Using Generating Functions to Solve Recursions] What are the five steps of solving a recursion for (an)(a_n)(an) with a generating function?
Set up A(z)A(z)A(z) with the recursion, express the sums by A(z)A(z)A(z) , solve for A(z)A(z)A(z) , partial fractions, compare coefficients. 1. Write A(z)=∑n≥0anznA(z) = \sum_{n \ge 0} a_n z^nA(z)=∑n≥0anzn and apply the recursion. 2. Replace the infinite sums on the right by A(z)A(z)A(z) . 3. Solve the equation for A(z)A(z)A(z) . 4. Write the solution as a power series, via partial fraction decomposition. 5. Read off ana_nan by comparing coefficients.
[Using Generating Functions to Solve Recursions] F(z)=∑n≥0FnznF(z) = \sum_{n \ge 0} F_n z^nF(z)=∑n≥0Fnzn is the generating function of the Fibonacci numbers ( F0=0F_0 = 0F0=0 , F1=1F_1 = 1F1=1 , Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}Fn=Fn−1+Fn−2 ). Which equation does the recursion give for F(z)F(z)F(z) ?
F(z)=z+zF(z)+z2F(z)\boldsymbol{F(z) = z + zF(z) + z^2 F(z)}F(z)=z+zF(z)+z2F(z) F(z)=F0+F1z+∑n≥0(Fn+1+Fn)zn+2=z+z∑n≥0Fn+1zn+1+z2∑n≥0FnznF(z) = F_0 + F_1 z + \sum_{n \ge 0} (F_{n+1} + F_n) z^{n+2} = z + z \sum_{n \ge 0} F_{n+1} z^{n+1} + z^2 \sum_{n \ge 0} F_n z^nF(z)=F0+F1z+∑n≥0(Fn+1+Fn)zn+2=z+z∑n≥0Fn+1zn+1+z2∑n≥0Fnzn .
[Using Generating Functions to Solve Recursions] F(z)=∑n≥0FnznF(z) = \sum_{n \ge 0} F_n z^nF(z)=∑n≥0Fnzn is the generating function of the Fibonacci numbers, F0=0F_0 = 0F0=0 . Why is z∑n≥0Fn+1zn+1\displaystyle z \sum_{n \ge 0} F_{n+1} z^{n+1}zn≥0∑Fn+1zn+1 equal to zF(z)zF(z)zF(z) ?
∑n≥0Fn+1zn+1=∑n≥1Fnzn=F(z)−F0z0\sum_{n \ge 0} F_{n+1} z^{n+1} = \sum_{n \ge 1} F_n z^n = F(z) - F_0 z^0∑n≥0Fn+1zn+1=∑n≥1Fnzn=F(z)−F0z0 , and F0=0F_0 = 0F0=0 .
[Using Generating Functions to Solve Recursions] What is the generating function F(z)=∑n≥0FnznF(z) = \sum_{n \ge 0} F_n z^nF(z)=∑n≥0Fnzn of the Fibonacci numbers, in closed form?
F(z)=z1−z−z2\displaystyle\boldsymbol{F(z) = \frac{z}{1 - z - z^2}}F(z)=1−z−z2z Solve F(z)=z+zF(z)+z2F(z)F(z) = z + zF(z) + z^2 F(z)F(z)=z+zF(z)+z2F(z) for F(z)F(z)F(z) .
[Using Generating Functions to Solve Recursions] Which ansatz does the partial fraction decomposition of z1−z−z2\displaystyle\frac{z}{1 - z - z^2}1−z−z2z use, and which two equations must it satisfy?
z1−z−z2=A1−αz+B1−βz\displaystyle\boldsymbol{\frac{z}{1-z-z^2} = \frac{A}{1-\alpha z} + \frac{B}{1-\beta z}}1−z−z2z=1−αzA+1−βzB , with (1−αz)(1−βz)=1−z−z2(1-\alpha z)(1-\beta z) = 1 - z - z^2(1−αz)(1−βz)=1−z−z2 and A(1−βz)+B(1−αz)=zA(1-\beta z) + B(1-\alpha z) = zA(1−βz)+B(1−αz)=z . Each summand is then a geometric series: A1−αz=∑n≥0Aαnzn\frac{A}{1-\alpha z} = \sum_{n \ge 0} A \alpha^n z^n1−αzA=∑n≥0Aαnzn .
[Using Generating Functions to Solve Recursions] Find α,β\alpha, \betaα,β with (1−αz)(1−βz)=1−z−z2(1-\alpha z)(1-\beta z) = 1 - z - z^2(1−αz)(1−βz)=1−z−z2 .
α=1+52, β=1−52\boldsymbol{\alpha = \frac{1+\sqrt5}{2}, \ \beta = \frac{1-\sqrt5}{2}}α=21+5, β=21−5 (or the other way round). Comparing coefficients: α+β=1\alpha + \beta = 1α+β=1 and αβ=−1\alpha\beta = -1αβ=−1 , so α2−α−1=0\alpha^2 - \alpha - 1 = 0α2−α−1=0 .
[Using Generating Functions to Solve Recursions] With α=1+52\alpha = \frac{1+\sqrt5}{2}α=21+5 and β=1−52\beta = \frac{1-\sqrt5}{2}β=21−5 , find A,BA, BA,B with A(1−βz)+B(1−αz)=zA(1-\beta z) + B(1-\alpha z) = zA(1−βz)+B(1−αz)=z .
A=15, B=−15\boldsymbol{A = \frac{1}{\sqrt5}, \ B = -\frac{1}{\sqrt5}}A=51, B=−51 Constant terms: A+B=0A + B = 0A+B=0 . Coefficients of zzz : −Aβ−Bα=A(α−β)=1-A\beta - B\alpha = A(\alpha - \beta) = 1−Aβ−Bα=A(α−β)=1 , and α−β=5\alpha - \beta = \sqrt5α−β=5 .
[Using Generating Functions to Solve Recursions] What is Binet's formula for the Fibonacci numbers FnF_nFn ?
Fn=15((1+52)n−(1−52)n)\displaystyle\boldsymbol{F_n = \frac{1}{\sqrt5} \left( \left( \frac{1+\sqrt5}{2} \right)^n - \left( \frac{1-\sqrt5}{2} \right)^n \right)}Fn=51((21+5)n−(21−5)n) From F(z)=1/51−1+52z−1/51−1−52zF(z) = \frac{1/\sqrt5}{1 - \frac{1+\sqrt5}{2} z} - \frac{1/\sqrt5}{1 - \frac{1-\sqrt5}{2} z}F(z)=1−21+5z1/5−1−21−5z1/5 and the geometric series, by comparing coefficients.
[Using Generating Functions to Solve Recursions] The number Φ=1+52≈1.618\Phi = \frac{1+\sqrt5}{2} \approx 1.618Φ=21+5≈1.618 is called the golden ratio.
It is the larger root of α2−α−1=0\alpha^2 - \alpha - 1 = 0α2−α−1=0 , and Binet's formula reads Fn=15(Φn−(1−Φ)n)F_n = \frac{1}{\sqrt5} \left( \Phi^n - (1 - \Phi)^n \right)Fn=51(Φn−(1−Φ)n) .
[Using Generating Functions to Solve Recursions] Recursion an=c1an−1+⋯+ckan−ka_n = c_1 a_{n-1} + \dots + c_k a_{n-k}an=c1an−1+⋯+ckan−k ( n≥kn \ge kn≥k ), generating function A(z)=∑n≥0anznA(z) = \sum_{n \ge 0} a_n z^nA(z)=∑n≥0anzn . What does ∑n≥kcjan−jzn\displaystyle\sum_{n \ge k} c_j a_{n-j} z^nn≥k∑cjan−jzn become in terms of A(z)A(z)A(z) ?
cjzj(A(z)−∑i=0k−j−1aizi)\displaystyle\boldsymbol{c_j z^j \left( A(z) - \sum_{i=0}^{k-j-1} a_i z^i \right)}cjzj(A(z)−i=0∑k−j−1aizi) ∑n≥kan−jzn=zj∑m≥k−jamzm\sum_{n \ge k} a_{n-j} z^n = z^j \sum_{m \ge k-j} a_m z^m∑n≥kan−jzn=zj∑m≥k−jamzm , which misses the terms m<k−jm < k - jm<k−j of A(z)A(z)A(z) . For j=kj = kj=k nothing is missing: ckzkA(z)c_k z^k A(z)ckzkA(z) .
[Using Generating Functions to Solve Recursions] For a homogeneous linear recursion an=c1an−1+⋯+ckan−ka_n = c_1 a_{n-1} + \dots + c_k a_{n-k}an=c1an−1+⋯+ckan−k ( n≥kn \ge kn≥k ) with given a0,…,ak−1a_0, \dots, a_{k-1}a0,…,ak−1 , what form does the generating function A(z)=∑n≥0anznA(z) = \sum_{n \ge 0} a_n z^nA(z)=∑n≥0anzn have?
A(z)=d0+d1z+⋯+dk−1zk−11−c1z−c2z2−⋯−ckzk\displaystyle\boldsymbol{A(z) = \frac{d_0 + d_1 z + \dots + d_{k-1} z^{k-1}}{1 - c_1 z - c_2 z^2 - \dots - c_k z^k}}A(z)=1−c1z−c2z2−⋯−ckzkd0+d1z+⋯+dk−1zk−1 for suitable d0,…,dk−1d_0, \dots, d_{k-1}d0,…,dk−1 . A polynomial of degree less than kkk over 1−c1z−⋯−ckzk1 - c_1 z - \dots - c_k z^k1−c1z−⋯−ckzk .
[Using Generating Functions to Solve Recursions] A(z)A(z)A(z) is a polynomial of degree less than kkk divided by 1−c1z−⋯−ckzk1 - c_1 z - \dots - c_k z^k1−c1z−⋯−ckzk . What form does its partial fraction decomposition have?
A(z)=∑i=1rgi(z)(1−αiz)mi\displaystyle\boldsymbol{A(z) = \sum_{i=1}^{r} \frac{g_i(z)}{(1 - \alpha_i z)^{m_i}}}A(z)=i=1∑r(1−αiz)migi(z) , each gig_igi a polynomial of degree at most mi−1m_i - 1mi−1 . Here 1−c1z−⋯−ckzk=(1−α1z)m1⋯(1−αrz)mr1 - c_1 z - \dots - c_k z^k = (1-\alpha_1 z)^{m_1} \cdots (1-\alpha_r z)^{m_r}1−c1z−⋯−ckzk=(1−α1z)m1⋯(1−αrz)mr : the αi\alpha_iαi are the distinct zeros of zk−c1zk−1−⋯−ckz^k - c_1 z^{k-1} - \dots - c_kzk−c1zk−1−⋯−ck , with multiplicities mim_imi .
[Using Generating Functions to Solve Recursions] A(z)=∑i=1rgi(z)(1−αiz)mi\displaystyle A(z) = \sum_{i=1}^{r} \frac{g_i(z)}{(1 - \alpha_i z)^{m_i}}A(z)=i=1∑r(1−αiz)migi(z) with gi(z)=∑j=0mi−1gijzjg_i(z) = \sum_{j=0}^{m_i - 1} g_{ij} z^jgi(z)=∑j=0mi−1gijzj . Which formula for 1(1−αz)m\frac{1}{(1-\alpha z)^m}(1−αz)m1 turns this into a power series, and what is the result?
1(1−αz)m=∑n≥0(n+m−1n)αnzn\displaystyle\boldsymbol{\frac{1}{(1-\alpha z)^m} = \sum_{n \ge 0} \binom{n+m-1}{n} \alpha^n z^n}(1−αz)m1=n≥0∑(nn+m−1)αnzn , so A(z)=∑i=1r∑j=0mi−1gij∑n≥0(n+mi−1n)αinzn+j\displaystyle A(z) = \sum_{i=1}^{r} \sum_{j=0}^{m_i-1} g_{ij} \sum_{n \ge 0} \binom{n+m_i-1}{n} \alpha_i^n z^{n+j}A(z)=i=1∑rj=0∑mi−1gijn≥0∑(nn+mi−1)αinzn+j . The first formula is (11−z)m=∑n≥0(m+n−1n)zn\left( \frac{1}{1-z} \right)^m = \sum_{n \ge 0} \binom{m+n-1}{n} z^n(1−z1)m=∑n≥0(nm+n−1)zn…
[Using Generating Functions to Solve Recursions] What is the reflected polynomial pRp^RpR of p(z)=1+e1z+e2z2+⋯+ekzkp(z) = 1 + e_1 z + e_2 z^2 + \dots + e_k z^kp(z)=1+e1z+e2z2+⋯+ekzk ?
pR(z)=zk+e1zk−1+e2zk−2+⋯+ek\boldsymbol{p^R(z) = z^k + e_1 z^{k-1} + e_2 z^{k-2} + \dots + e_k}pR(z)=zk+e1zk−1+e2zk−2+⋯+ek The coefficients in reverse order. Then p(z)=zkpR ⁣(1z)p(z) = z^k p^R\!\left( \frac{1}{z} \right)p(z)=zkpR(z1) .
[Using Generating Functions to Solve Recursions] p(z)=1+e1z+⋯+ekzkp(z) = 1 + e_1 z + \dots + e_k z^kp(z)=1+e1z+⋯+ekzk has reflected polynomial pR(z)=zk+e1zk−1+⋯+ekp^R(z) = z^k + e_1 z^{k-1} + \dots + e_kpR(z)=zk+e1zk−1+⋯+ek with zeros α1,…,αk\alpha_1, \dots, \alpha_kα1,…,αk . Factor p(z)p(z)p(z) .
p(z)=(1−α1z)⋯(1−αkz)\boldsymbol{p(z) = (1 - \alpha_1 z) \cdots (1 - \alpha_k z)}p(z)=(1−α1z)⋯(1−αkz) p(z)=zkpR ⁣(1z)=zk(1z−α1)⋯(1z−αk)p(z) = z^k p^R\!\left( \frac{1}{z} \right) = z^k \left( \frac{1}{z} - \alpha_1 \right) \cdots \left( \frac{1}{z} - \alpha_k \right)p(z)=zkpR(z1)=zk(z1−α1)⋯(z1−αk) . So the zeros of pRp^RpR give the denominators of the partial fraction decomposition.
[Using Generating Functions to Solve Recursions] In a partial fraction decomposition of q(z)(1−α1z)⋯(1−αkz)\frac{q(z)}{(1-\alpha_1 z) \cdots (1-\alpha_k z)}(1−α1z)⋯(1−αkz)q(z) with known αi\alpha_iαi , how are the numerators found?
By comparing coefficients of polynomials: a linear system of kkk equations in kkk unknowns.
[Using Generating Functions to Solve Recursions] Which polynomial do you factor to solve the Fibonacci recursion Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}Fn=Fn−1+Fn−2 , and what are its zeros?
The reflected polynomial z2−z−1z^2 - z - 1z2−z−1 of the denominator 1−z−z21 - z - z^21−z−z2 ; zeros 1±52\boldsymbol{\frac{1 \pm \sqrt5}{2}}21±5 . So 1−z−z2=(1−1+52z)(1−1−52z)1 - z - z^2 = \left( 1 - \frac{1+\sqrt5}{2} z \right) \left( 1 - \frac{1-\sqrt5}{2} z \right)1−z−z2=(1−21+5z)(1−21−5z) .
[Using Generating Functions to Solve Recursions] Solve a0=0a_0 = 0a0=0 , a1=1a_1 = 1a1=1 , an=3an−1−2an−2a_n = 3a_{n-1} - 2a_{n-2}an=3an−1−2an−2 ( n≥2n \ge 2n≥2 ) with a generating function.
an=2n−1\boldsymbol{a_n = 2^n - 1}an=2n−1 A(z)=z1−3z+2z2=z(1−z)(1−2z)=11−2z−11−zA(z) = \frac{z}{1 - 3z + 2z^2} = \frac{z}{(1-z)(1-2z)} = \frac{1}{1-2z} - \frac{1}{1-z}A(z)=1−3z+2z2z=(1−z)(1−2z)z=1−2z1−1−z1 . Check: 0,1,3,70, 1, 3, 70,1,3,7 .
[Using Generating Functions to Solve Recursions] Solve a0=0a_0 = 0a0=0 , a1=1a_1 = 1a1=1 , an=2an−1−an−2a_n = 2a_{n-1} - a_{n-2}an=2an−1−an−2 ( n≥2n \ge 2n≥2 ) with a generating function. What is special about the partial fractions?
an=n\boldsymbol{a_n = n}an=n . The denominator has a double zero: 1−2z+z2=(1−z)21 - 2z + z^2 = (1-z)^21−2z+z2=(1−z)2 . A(z)=z(1−z)2=∑n≥0nznA(z) = \frac{z}{(1-z)^2} = \sum_{n \ge 0} n z^nA(z)=(1−z)2z=∑n≥0nzn .
[Using Generating Functions to Solve Recursions] What is a system of simultaneous recursions?
Recursions for two sequences (an)(a_n)(an) , (bn)(b_n)(bn) where ana_nan may depend on b1,…,bn−1b_1, \dots, b_{n-1}b1,…,bn−1 and bnb_nbn on a1,…,an−1a_1, \dots, a_{n-1}a1,…,an−1 . They can be solved with one generating function per sequence. (This part of the notes was not covered in the lecture.)
[Using Generating Functions to Solve Recursions] (2+3)2n=an+bn6(\sqrt2 + \sqrt3)^{2n} = a_n + b_n \sqrt6(2+3)2n=an+bn6 with an,bn∈Na_n, b_n \in \mathbb{N}an,bn∈N , a0=1a_0 = 1a0=1 , b0=0b_0 = 0b0=0 . Which recursions do an,bna_n, b_nan,bn satisfy for n≥1n \ge 1n≥1 ?
an=5an−1+12bn−1,bn=2an−1+5bn−1\boldsymbol{a_n = 5a_{n-1} + 12 b_{n-1}, \quad b_n = 2a_{n-1} + 5b_{n-1}}an=5an−1+12bn−1,bn=2an−1+5bn−1 (2+3)2=5+26(\sqrt2 + \sqrt3)^2 = 5 + 2\sqrt6(2+3)2=5+26 , and (an−1+bn−16)(5+26)=(5an−1+12bn−1)+(2an−1+5bn−1)6(a_{n-1} + b_{n-1}\sqrt6)(5 + 2\sqrt6) = (5a_{n-1} + 12b_{n-1}) + (2a_{n-1} + 5b_{n-1})\sqrt6(an−1+bn−16)(5+26)=(5an−1+12bn−1)+(2an−1+5bn−1)6 . This induction also proves that such an,bn∈Na_n, b_n \in \mathbb{N}an,bn∈N exist.
[Using Generating Functions to Solve Recursions] a0=1a_0 = 1a0=1 , b0=0b_0 = 0b0=0 , an=5an−1+12bn−1a_n = 5a_{n-1} + 12 b_{n-1}an=5an−1+12bn−1 , bn=2an−1+5bn−1b_n = 2a_{n-1} + 5b_{n-1}bn=2an−1+5bn−1 ( n≥1n \ge 1n≥1 ). With A(z)=∑anznA(z) = \sum a_n z^nA(z)=∑anzn , B(z)=∑bnznB(z) = \sum b_n z^nB(z)=∑bnzn : which equations hold, and what is A(z)A(z)A(z) ?
A=1+5zA+12zB, B=2zA+5zB\boldsymbol{A = 1 + 5zA + 12zB, \ B = 2zA + 5zB}A=1+5zA+12zB, B=2zA+5zB , so A(z)=1−5z1−10z+z2\displaystyle\boldsymbol{A(z) = \frac{1 - 5z}{1 - 10z + z^2}}A(z)=1−10z+z21−5z . The second equation gives B=2zA1−5zB = \frac{2zA}{1-5z}B=1−5z2zA ; substituting: A((1−5z)2−24z2)=1−5zA \left( (1-5z)^2 - 24z^2 \right) = 1 - 5zA((1−5z)2−24z2)=1−5z .
[Using Generating Functions to Solve Recursions] Find ana_nan from ∑n≥0anzn=1−5z1−10z+z2\displaystyle\sum_{n \ge 0} a_n z^n = \frac{1 - 5z}{1 - 10z + z^2}n≥0∑anzn=1−10z+z21−5z .
an=12((5+26)n+(5−26)n)\boldsymbol{a_n = \frac{1}{2} \left( (5 + 2\sqrt6)^n + (5 - 2\sqrt6)^n \right)}an=21((5+26)n+(5−26)n) 1−10z+z2=(1−(5+26)z)(1−(5−26)z)1 - 10z + z^2 = (1 - (5+2\sqrt6)z)(1 - (5-2\sqrt6)z)1−10z+z2=(1−(5+26)z)(1−(5−26)z) , and the partial fractions are 1/21−(5+26)z+1/21−(5−26)z\frac{1/2}{1 - (5+2\sqrt6)z} + \frac{1/2}{1 - (5-2\sqrt6)z}1−(5+26)z1/2+1−(5−26)z1/2 .
[Using Generating Functions to Solve Recursions] What is the digit right after the decimal point of (2+3)1980(\sqrt2 + \sqrt3)^{1980}(2+3)1980 ?
9\boldsymbol{9}9 (2+3)1980=(5+26)990(\sqrt2 + \sqrt3)^{1980} = (5 + 2\sqrt6)^{990}(2+3)1980=(5+26)990 is an integer minus the tiny number (5−26)990(5 - 2\sqrt6)^{990}(5−26)990 .
[Using Generating Functions to Solve Recursions] (2+3)2n=(5+26)n=an+bn6(\sqrt2 + \sqrt3)^{2n} = (5 + 2\sqrt6)^n = a_n + b_n\sqrt6(2+3)2n=(5+26)n=an+bn6 with an,bn∈Na_n, b_n \in \mathbb{N}an,bn∈N , and an=12((5+26)n+(5−26)n)a_n = \frac{1}{2} \left( (5 + 2\sqrt6)^n + (5 - 2\sqrt6)^n \right)an=21((5+26)n+(5−26)n) .Why is the first digit after the decimal point of (2+3)1980(\sqrt2 + \sqrt3)^{1980}(2+3)1980 a 9?
an=bn6+(5−26)na_n = b_n\sqrt6 + (5 - 2\sqrt6)^nan=bn6+(5−26)n with ana_nan an integer and 0<(5−26)990<0.119900 < (5 - 2\sqrt6)^{990} < 0.11^{990}0<(5−26)990<0.11990 , so b9906b_{990}\sqrt6b9906 is just below an integer. Substitute (5+26)n=an+bn6(5+2\sqrt6)^n = a_n + b_n\sqrt6(5+26)n=an+bn6 into the formula for ana_nan . So the digits of b9906b_{990}\sqrt6b9906 after the decimal point start with many 9s, and adding the integer a990a_{990}a990 keeps them: a990+b9906=(2+3)1980a_{99…
[Exponential Generating Functions] What is the exponential generating function A^(z)\hat A(z)A^(z) of a sequence (an)n∈N(a_n)_{n \in \mathbb{N}}(an)n∈N ?
A^(z)=∑n≥0ann!zn\displaystyle\boldsymbol{\hat A(z) = \sum_{n \ge 0} \frac{a_n}{n!} z^n}A^(z)=n≥0∑n!anzn The ordinary generating function of (ann!)n∈N\left( \frac{a_n}{n!} \right)_{n \in \mathbb{N}}(n!an)n∈N , so all results on generating functions apply.
[Exponential Generating Functions] A^\hat AA^ , B^\hat BB^ , C^\hat CC^ are the exponential generating functions of (an)(a_n)(an) , (bn)(b_n)(bn) , (cn)(c_n)(cn) . When does C^(z)=A^(z)B^(z)\hat C(z) = \hat A(z) \hat B(z)C^(z)=A^(z)B^(z) hold?
If and only if cn=∑k=0n(nk)akbn−k\displaystyle\boldsymbol{c_n = \sum_{k=0}^{n} \binom{n}{k} a_k b_{n-k}}cn=k=0∑n(kn)akbn−k for all n∈Nn \in \mathbb{N}n∈N . (cnn!)\left( \frac{c_n}{n!} \right)(n!cn) must be the convolution of (ann!)\left( \frac{a_n}{n!} \right)(n!an) and (bnn!)\left( \frac{b_n}{n!} \right)(n!bn) : cnn!=∑k=0nakk!bn−k(n−k)!\frac{c_n}{n!} = \sum_{k=0}^{n} \frac{a_k}{k!} \frac{b_{n-k}}{(n-k)!}n!cn=∑k=0nk!ak(n−k)!bn−k . Multiply by n!n!n! .
[Exponential Generating Functions] The equivalence of C^(z)=A^(z)B^(z)\hat C(z) = \hat A(z) \hat B(z)C^(z)=A^(z)B^(z) for exponential generating functions with cn=∑k=0n(nk)akbn−kc_n = \sum_{k=0}^{n} \binom{n}{k} a_k b_{n-k}cn=∑k=0n(kn)akbn−k is called binomial convolution.
[Exponential Generating Functions] Which sequence has the exponential generating function eaze^{az}eaz ?
an\boldsymbol{a^n}an , i.e. eaz=∑n≥0ann!zn\displaystyle e^{az} = \sum_{n \ge 0} \frac{a^n}{n!} z^neaz=n≥0∑n!anzn . The Taylor series of the exponential function. For a=1a = 1a=1 : eze^zez is the exponential generating function of 1,1,1,…1, 1, 1, \dots1,1,1,…
[Exponential Generating Functions] How does binomial convolution prove the binomial theorem (a+b)n=∑k=0n(nk)akbn−k(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}(a+b)n=∑k=0n(kn)akbn−k ?
eaz⋅ebz=e(a+b)ze^{az} \cdot e^{bz} = e^{(a+b)z}eaz⋅ebz=e(a+b)z , and these are the exponential generating functions of ana^nan , bnb^nbn , (a+b)n(a+b)^n(a+b)n . Binomial convolution: C^=A^B^\hat C = \hat A \hat BC^=A^B^ if and only if cn=∑k=0n(nk)akbn−kc_n = \sum_{k=0}^{n} \binom{n}{k} a_k b_{n-k}cn=∑k=0n(kn)akbn−k .
[Exponential Generating Functions] (1+z)a(1+z)^a(1+z)a is the exponential generating function of which sequence?
The falling factorials an‾=a(a−1)⋯(a−n+1)\boldsymbol{a^{\underline{n}} = a(a-1) \cdots (a-n+1)}an=a(a−1)⋯(a−n+1) . (1+z)a=∑n≥0(an)zn(1+z)^a = \sum_{n \ge 0} \binom{a}{n} z^n(1+z)a=∑n≥0(na)zn and (an)=an‾n!\binom{a}{n} = \frac{a^{\underline{n}}}{n!}(na)=n!an .
[Exponential Generating Functions] How does binomial convolution prove the Vandermonde identity (a+bn)=∑k=0n(ak)(bn−k)\displaystyle\binom{a+b}{n} = \sum_{k=0}^{n} \binom{a}{k} \binom{b}{n-k}(na+b)=k=0∑n(ka)(n−kb) ?
(1+z)a(1+z)b=(1+z)a+b(1+z)^a (1+z)^b = (1+z)^{a+b}(1+z)a(1+z)b=(1+z)a+b , and (1+z)a(1+z)^a(1+z)a is the exponential generating function of the falling factorials an‾a^{\underline{n}}an . So (a+b)n‾=∑k=0n(nk)ak‾bn−k‾(a+b)^{\underline{n}} = \sum_{k=0}^{n} \binom{n}{k} a^{\underline{k}} b^{\underline{n-k}}(a+b)n=∑k=0n(kn)akbn−k ; divide by n!n!n! .
[Exponential Generating Functions] DnD_nDn is the number of derangements of {1,…,n}\{1, \dots, n\}{1,…,n} (permutations without fixed points), with D0=1D_0 = 1D0=1 .Why does n!=∑k=0n(nk)Dk\displaystyle n! = \sum_{k=0}^{n} \binom{n}{k} D_kn!=k=0∑n(kn)Dk hold?
(nk)Dk\binom{n}{k} D_k(kn)Dk counts the permutations of {1,…,n}\{1, \dots, n\}{1,…,n} with exactly n−kn - kn−k fixed points. Choose the kkk elements that are not fixed and derange them.
[Exponential Generating Functions] DnD_nDn is the number of derangements of {1,…,n}\{1, \dots, n\}{1,…,n} (permutations without fixed points), with D0=1D_0 = 1D0=1 . n!=∑k=0n(nk)Dk\displaystyle n! = \sum_{k=0}^{n} \binom{n}{k} D_kn!=k=0∑n(kn)Dk .What does this give for the exponential generating function D^(z)=∑n≥0Dnn!zn\hat D(z) = \sum_{n \ge 0} \frac{D_n}{n!} z^nD^(z)=∑n≥0n!Dnzn ?
D^(z)⋅ez=11−z\boldsymbol{\hat D(z) \cdot e^z = \frac{1}{1-z}}D^(z)⋅ez=1−z1 , so D^(z)=e−z1−z\displaystyle\boldsymbol{\hat D(z) = \frac{e^{-z}}{1-z}}D^(z)=1−ze−z . (n!)(n!)(n!) is the binomial convolution of (Dn)(D_n)(Dn) with 1,1,1,…1, 1, 1, \dots1,1,1,… , whose exponential generating function is eze^zez ; and ∑n≥0n!n!zn=11−z\sum_{n \ge 0} \frac{n!}{n!} z^n = \frac{1}{1-z}∑n≥0n!n!zn=1−z1 .
[Exponential Generating Functions] DnD_nDn is the number of derangements of {1,…,n}\{1, \dots, n\}{1,…,n} (permutations without fixed points), with D0=1D_0 = 1D0=1 .How do you read off DnD_nDn from ∑n≥0Dnn!zn=e−z1−z\displaystyle\sum_{n \ge 0} \frac{D_n}{n!} z^n = \frac{e^{-z}}{1-z}n≥0∑n!Dnzn=1−ze−z ?
As a product of ordinary generating functions: Dnn!=∑k=0n(−1)kk!\displaystyle\boldsymbol{\frac{D_n}{n!} = \sum_{k=0}^{n} \frac{(-1)^k}{k!}}n!Dn=k=0∑nk!(−1)k . e−z=∑n≥0(−1)nn!zne^{-z} = \sum_{n \ge 0} \frac{(-1)^n}{n!} z^ne−z=∑n≥0n!(−1)nzn and 11−z=∑n≥0zn\frac{1}{1-z} = \sum_{n \ge 0} z^n1−z1=∑n≥0zn ; multiplying by 11−z\frac{1}{1-z}1−z1 turns coefficients into their partial sums.
[Exponential Generating Functions] ana_nan is the number of maps f:{1,…,n}→{1,…,n}f: \{1, \dots, n\} \to \{1, \dots, n\}f:{1,…,n}→{1,…,n} whose image is {1,…,j}\{1, \dots, j\}{1,…,j} for some jjj ( a0=1a_0 = 1a0=1 ). What is a2a_2a2 , and which maps are counted?
a2=3\boldsymbol{a_2 = 3}a2=3 : the map sending 1 and 2 to 1, and the two permutations of {1,2}\{1, 2\}{1,2} . The map sending both to 2 has image {2}\{2\}{2} , which is not of the form {1,…,j}\{1, \dots, j\}{1,…,j} .
[Exponential Generating Functions] ana_nan is the number of maps f:{1,…,n}→{1,…,n}f: \{1, \dots, n\} \to \{1, \dots, n\}f:{1,…,n}→{1,…,n} whose image is {1,…,j}\{1, \dots, j\}{1,…,j} for some jjj ; a0=1a_0 = 1a0=1 .Which recursion holds for n≥1n \ge 1n≥1 , and why?
an=∑k=1n(nk)an−k\displaystyle\boldsymbol{a_n = \sum_{k=1}^{n} \binom{n}{k} a_{n-k}}an=k=1∑n(kn)an−k Let k≥1k \ge 1k≥1 be the number of elements mapped to 1: choose them in (nk)\binom{n}{k}(kn) ways; the other n−kn - kn−k elements must be mapped onto some {2,…,j}\{2, \dots, j\}{2,…,j} , in an−ka_{n-k}an−k ways.
[Exponential Generating Functions] ana_nan is the number of maps f:{1,…,n}→{1,…,n}f: \{1, \dots, n\} \to \{1, \dots, n\}f:{1,…,n}→{1,…,n} whose image is {1,…,j}\{1, \dots, j\}{1,…,j} for some jjj ; a0=1a_0 = 1a0=1 , a1=1a_1 = 1a1=1 , a2=3a_2 = 3a2=3 , and an=∑k=1n(nk)an−ka_n = \sum_{k=1}^{n} \binom{n}{k} a_{n-k}an=∑k=1n(kn)an−k for n≥1n \ge 1n≥1 .Compute a3a_3a3 .
a3=13\boldsymbol{a_3 = 13}a3=13 (31)a2+(32)a1+(33)a0=9+3+1\binom31 a_2 + \binom32 a_1 + \binom33 a_0 = 9 + 3 + 1(13)a2+(23)a1+(33)a0=9+3+1 .
[Exponential Generating Functions] a0=1a_0 = 1a0=1 and an=∑k=1n(nk)an−ka_n = \sum_{k=1}^{n} \binom{n}{k} a_{n-k}an=∑k=1n(kn)an−k for n≥1n \ge 1n≥1 . Which equation does the exponential generating function A^(z)=∑n≥0ann!zn\hat A(z) = \sum_{n \ge 0} \frac{a_n}{n!} z^nA^(z)=∑n≥0n!anzn satisfy?
2A^(z)=ezA^(z)+1\boldsymbol{2\hat A(z) = e^z \hat A(z) + 1}2A^(z)=ezA^(z)+1 , so A^(z)=12−ez\displaystyle\boldsymbol{\hat A(z) = \frac{1}{2 - e^z}}A^(z)=2−ez1 . Adding the summand k=0k = 0k=0 (which is ana_nan ) to both sides: 2an=∑k=0n(nk)an−k+[n=0]2a_n = \sum_{k=0}^{n} \binom{n}{k} a_{n-k} + [n = 0]2an=∑k=0n(kn)an−k+[n=0] , a binomial convolution with 1,1,1,…1, 1, 1, \dots1,1,1,… (exponential generating function eze^zez ). The +1+1+1 fixes n=0n = 0n=0 , where the sum is a0=1a_0 = 1a0=1…
[Exponential Generating Functions] Expand 12−ez\displaystyle\frac{1}{2 - e^z}2−ez1 as an exponential generating function. What is the coefficient sequence ana_nan ?
an=∑k≥0kn2k+1\displaystyle\boldsymbol{a_n = \sum_{k \ge 0} \frac{k^n}{2^{k+1}}}an=k≥0∑2k+1kn 12−ez=12⋅11−ez2=12∑k≥0(ez2)k=∑k≥012k+1∑n≥0knznn!\displaystyle\frac{1}{2 - e^z} = \frac12 \cdot \frac{1}{1 - \frac{e^z}{2}} = \frac12 \sum_{k \ge 0} \left( \frac{e^z}{2} \right)^k = \sum_{k \ge 0} \frac{1}{2^{k+1}} \sum_{n \ge 0} \frac{k^n z^n}{n!}2−ez1=21⋅1−2ez1=21k≥0∑(2ez)k=k≥0∑2k+11n≥0∑n!knzn
[Exponential Generating Functions] Why is ∑k≥0kn2k+1\displaystyle\sum_{k \ge 0} \frac{k^n}{2^{k+1}}k≥0∑2k+1kn a natural number for every n∈Nn \in \mathbb{N}n∈N ?
The sum equals the number ana_nan of maps f:{1,…,n}→{1,…,n}f: \{1, \dots, n\} \to \{1, \dots, n\}f:{1,…,n}→{1,…,n} whose image is {1,…,j}\{1, \dots, j\}{1,…,j} for some jjj . Both have the exponential generating function 12−ez\frac{1}{2 - e^z}2−ez1 . e.g. n=2n = 2n=2 : ∑k≥0k22k+1=3\sum_{k \ge 0} \frac{k^2}{2^{k+1}} = 3∑k≥02k+1k2=3 .