Sequences and Generating Functions

# Sequences and Generating Functions ## Building Generating Functions In some circustances, we utilize a function to encode an infinite sequence. Specifically, we look at a function whose power series “displays” the terms of the sequence. For example, we would look at the power series $1+x+2x^2+3x^3+5x^4+8x^5+\cdots$ which displays the sequence $1, 1, 2, 3, 5, 8, \cdots$ as coefficients. Since an infinite power series is simply an infinite sum of terms of the form $c_nx^n$ where $c_n$ is some constant, we might write a power series as: $\qquad\qquad\qquad\sum_{k=0}^{\infty}c_kx^k$, or expand it as $\qquad\qquad\qquad c_0+c_1x+c_2x^2+c_3x^3+c_4x^4+\cdots$. In the context of generating functions, we call such a power series a $generating\ series$. The generating series generates the sequence $\qquad\qquad\qquad c_0,\ c_1x,\ c_2x^2,\ c_3x^3,\ c_4x^4,\ \cdots$ . In other words, the sequence generated by a generating series is simply the sequence of coefficients of the infinite polynomial. --- ### $Definition\ 1.\ Ordinary\ generating\ function$ :::info Let $\{a_k\}_0^\infty = \{a_0, a_1, ... \}$ be a series. Function \begin{aligned} f(x) = a_0+a_1x+a_2x^2+a_3x^3+\ ...\ =\displaystyle\sum_{k=0}^{\infty}a_kx^k \end{aligned} is the $ordinary\ generating\ function$ of $\{a_k\}_0^\infty$. ::: ::: This particular series $\{1\}_0^\infty$, i.e., $1, 1, 1, ...$ is really just a $geometric\ series$ with common ratio $x$ (註：可視其為公比為 $x$ 的等比級數). Let $S= 1 + x + x^2 + x^3 + \cdots$. We have \begin{align*} S & = 1 + x + x^2 + x^3 + \cdots\\ \underline{- x\ S} & \underline{\,\, = ~~~~~~ x + x^2 + x^3 + x^4 + \cdots}\\ (1-x)S &= 1 \\ S &= \dfrac{1}{1-x}. \\ \end{align*} :::warning $\dfrac{1}{1-x} (= 1+x+x^2+x^3+\ \cdots\ =\displaystyle\sum_{k=0}^{\infty}x^k)$ generates $1, 1, 1, 1, \cdots$ . ::: If we replace $x$ by $-x$, we get \begin{align*} \dfrac{1}{1-(-x)}=\dfrac{1}{1+x}&=1 + (-x) + (-x)^2 + (-x)^3 + \cdots \\ &=1 -x + x^2 -x^3 + \cdots. \end{align*} :::warning $\dfrac{1}{1+x} (= 1-x+x^2-x^3+\ \cdots)$ generates $1,−1, 1,−1,\cdots$. ::: If we replace $x$ by $3x$, we acquire $\qquad\qquad \dfrac{1}{1-3x}=1 + 3x + 9x^2 + 27x^3 + \cdots$ which generates $1,3, 9,27,\cdots$. By replacing $x$ in $\dfrac{1}{1-x}$ we can get generating functions for a variety of sequences. In general, if we replace $x$ in $\dfrac{1}{1-x}$ by $rx$, $\dfrac{1}{1-rx}$ generates $1, r, r^2, r^3,\cdots$. :::warning #### The generating function of $\{r^k\}_0^\infty$ is \begin{aligned} f(x) = 1+rx+r^2x^2+x^3+\ \cdots\ =\displaystyle\sum_{k=0}^{\infty}r^kx^k=\dfrac{1}{1-rx} \end{aligned} 註：可視其為公比為 $rx$ 的等比級數。 ::: In addition, we may multiply a constant to a generating function to produce m. For instance, each term of $2, 2, 2, \cdots$ is the result of multiplying the terms of $1, 1, 1, \cdots$ by constant 2. we have $\qquad\qquad \dfrac{2}{1-x}=2+2x+2x^2+2x^3+2x^4+\cdots$, which generates $2, 2, 2, \cdots$. As aforementioned, $\frac{1}{1-3x}$ generates $1,3, 9,27,\cdots$. We obtain $\qquad\qquad \dfrac{3}{1-3x}=3\cdot 1+3\cdot3x+3\cdot9x^2+3\cdot27x^3+\cdots$, which generates $3, 9, 27, 81, \cdots$. What about the sequence $2, 4, 10, 28, 82, \cdots$? Observe that each term in this seqeunce is 1 more than power of 3. That means we may add $1, 1, 1, 1, \cdots$ and $1,3, 9,27,\cdots$ to acquire the generating function for $2, 4, 10, 28, 82, \cdots$. That is, $\qquad\qquad 2+4x+10x^2+28x^3+82x^4+\cdots$ $\qquad\quad = (1+1)+(1+3)x+(1+9)x^2+(1+27)x^3+(1+81)x^4+\cdots$ $\qquad\quad = (1+x+x^2+x^3+\cdots)+(1+3x+9x^2+27x^3+\cdots)$ $\qquad\quad = \dfrac{1}{1-x}+\dfrac{1}{1-3x}$. On condition that we replace $x$ by $x^2$ in $\frac{1}{1-x}$, we get $\qquad\qquad \dfrac{1}{1-x^2}=1+x^2+x^4+x^6+\cdots$, which generates $1, 0, 1, 0, 1, 0,\cdots$. To $shift$ right the resultant series, we simply multiply $x$ onto $\frac{1}{1-x^2}$: $\qquad\qquad \dfrac{x}{1-x^2}=x+x^3+x^5+x^7+\cdots$, which generates $0, 1, 0, 1, 0,1,\cdots$. Of course, adding serieses $1,0,1,0,1,0,\cdots$ and $0,1,0,1,0,1,\cdots$ produces $1,1,1,1,1,1,\cdots$. Adding their corresponding generating functions retains the same effect: $\qquad\qquad \dfrac{1}{1-x^2}+\dfrac{x}{1-x^2}=\dfrac{1}{1-x}$. What if we take the $derivative$ of $\frac{1}{1-x}$? Owing to $\qquad\qquad \dfrac{\partial}{\partial x}(\dfrac{1}{1-x}) = \dfrac{\partial}{\partial x}(1-x)^{-1}= (-1)(1-x)^{-2}(-1)=\dfrac{1}{(1-x)^2}$ $\qquad\qquad \dfrac{\partial}{\partial x}(1+x+x^2+x^3+\cdots) = 1+2x+3x^2+4x^3+\cdots$, we know that :::warning $\dfrac{1}{(1-x)^2}=\displaystyle\sum_{k=0}^\infty kx^k$ generates $1, 2, 3, 4,\cdots$. The coefficient of term $x^k$ is $k$. ::: Take a second derivative: $\qquad\dfrac{\partial^2}{\partial x^2}(\dfrac{1}{1-x})=\dfrac{\partial}{\partial x}(\dfrac{1}{(1-x)^2})=\dfrac{2}{(1-x)^3}$ $\qquad\dfrac{\partial^2}{\partial x^2}(1+x+x^2+x^3+\cdots)=\dfrac{\partial}{\partial x}({1+2x+3x^2+4x^3+\cdots})$ $\qquad=1\cdot 2x+2\cdot 3x^2+3\cdot 4x^3+\cdots=2+6x+12x^2+20x^3+\cdots.$ That is, $\qquad\dfrac{2}{(1-x)^3}=2+6x+12x^2+20x^3+\cdots=\displaystyle\sum_{k=0}^\infty k(k+1)x^k.$ :::warning $\dfrac{1}{(1-x)^3}=1+3x+6x^2+10x^3+\cdots=\displaystyle\sum_{k=0}^\infty \frac{k(k+1)}{2}x^k$ generates $1, 3, 6, 10,\cdots$ ($triangular\ numbers$). The coefficient of term $x^k$ is $\dfrac{k(k+1)}{2}$. ::: Note that regarding series $S$ with its generating function $A$, $\frac{1}{1-x}A$ generates the prefix-sum series of $S$. $\frac{1}{1-x}$ is also called the $summation\ operator$ for generating functions. :::success Given series $A:\ a_0, a_1, a_2, \cdots$ with generating function $g(x)$, $\frac{1}{1-x}g(x)$ generates $S: a_0, a_1+a_0, a_2+a_1+a_0, \cdots$, which is the prefixs-sum series of $A$. ::: ex. For generating function \begin{matrix} &\dfrac{x^2}{3+2x}=\dfrac{x^2}{3}(\dfrac{1}{1+\frac{2}{3}x})=\dfrac{x^2}{3}(\dfrac{1}{1-(-\frac{2}{3}x)}) \\ &=\dfrac{x^2}{3}(1+(-\dfrac{2}{3})x+(-\dfrac{2}{3})^2x^2+(-\dfrac{2}{3})^3x^3+\ ...) \\ &=\dfrac{1}{3}(x^2+(-\dfrac{2}{3})x^3+(-\dfrac{2}{3})^2x^2+(-\dfrac{2}{3})^3x^3+\ ...\ ), \end{matrix} which generates series $0, 0, \dfrac{1}{3},\ \dfrac{1}{3}(-\dfrac{2}{3}),\ \dfrac{1}{3}(-\dfrac{2}{3})^2,\dfrac{1}{3}(-\dfrac{2}{3})^3,\ ...$ . Based on the fact that $\qquad\qquad (1+x)^n = \binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\ \cdots\ +\binom{n}{n}x^n$, we have the following result. :::warning #### The generating function of $\binom{n}{0}, \binom{n}{1}, \binom{n}{2}, ... , \binom{n}{n}$, for $n\gt 0$ is \begin{aligned} f(x) = \binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\ \cdots\ +\binom{n}{n}x^n\ =\displaystyle\sum_{k=0}^{\infty}\binom{n}{k}x^k=(1+x)^n \end{aligned} $(1+x)^n$ generates $\binom{n}{0}, \binom{n}{1}, \binom{n}{2},\cdots, \binom{n}{n}$ for $n\gt 0$. Note that the resultant $(1+x)^n$ is based on the Binomial theorem. ::: For $a\in \mathbb{R}$, the $Maclaurin\ series$ expansion for $(1+x)^a$ is given by \begin{align*} (1+x)^a & = 1 + ax + \frac{a(a-1)x^2}{2!} + \frac{a(a-1)(a-2)}{3!}x^3 + \cdots\\ &= 1+ \sum_{k=1}^\infty\dfrac{a(a-1)(a-2)\cdots(a-k+1)}{k!}x^k\\ &= \sum_{k=0}^\infty\binom{a}{k}x^k. \\ \end{align*} :::danger It is a generalized form of Binomial theorem. We call it *generalized Binomial theorem*, i.e., $$(1+x)^a = \sum_{k=0}^\infty\binom{a}{k}x^k\ \text{for }a\in \mathbb{R}\text{ and }k\in \{0, 1, 2, ...\}.$$ $(1+x)^n$ generates $\binom{n}{0}, \binom{n}{1}, \binom{n}{2},\cdots$ for $n\in \mathbb{R}$. ::: If $a\ (=n)\gt 0$, the above formula is exactly the Binomial theorem: \begin{align*} (1+x)^n & = \sum_{k=0}^n\binom{n}{k}x^k. \end{align*} On the contrary, $a\ (=-n)\lt 0$, the above formula follows the generalized Binomial theorem: \begin{align*} (1+x)^a = (1+x)^{-n}& = \sum_{k=0}^\infty\binom{-n}{k}x^k. \end{align*} The expansion of $(1+x)^n$ is valid for >(a) finite terms determined by the Binomial Theorem for *non-negative integer values of $n$* ($n\ge 0$); and (b) infinite terms determined by the Generalized Binomial Theorem for *all real or complex values of* $n$. Suppose that $a=-n$ where $n\in \mathbb{N}$ (or equivalently, $a$ is negtive). We have \begin{align*} \dbinom{-n}{k} & = \dfrac{(-n)(-n-1)(-n-2)\cdots(-n-k+1)}{k!}\\ &= \dfrac{(-n)(-(n+1))(-(n+2))\cdots(-(n+k-1))}{k!} \\ &= \dfrac{(-1)^k(n)(n+1)(n+2)\cdots(n+k-1)}{k!}\\ &= \dfrac{(-1)^k\underline{(n-1)!}(n)(n+1)(n+2)\cdots(n+k-1)}{\underline{(n-1)!}k!}\\ &= \dfrac{(-1)^k(n+k-1)!}{{(n-1)!}k!} = \dfrac{(-1)^k(n+k-1)!}{((n+k-1)-k)k!}\\ &= (-1)^k\binom{n+k-1}{k}.\\ \end{align*} That is, \begin{aligned} (1+x)^{-n}&=\binom{-n}{0}+\binom{-n}{1}x+\binom{-n}{2}x^2+\cdots \\ &=\sum_{k=0}^\infty\binom{-n}{k}x^k \\ &=\sum_{k=0}^\infty(-1)^k\binom{n+k-1}{k}x^k. \end{aligned} :::warning $(1+x)^{-n}$ generates $\binom{-n}{0}, \binom{-n}{1}, \binom{-n}{2},\cdots$ for $n\in \mathbb{R}$. ::: Note that \begin{align*} \dfrac{1}{(1-x)^n} & = (1+(-x))^{-n} \\ &= \sum_{k=0}^\infty(-1)^k\binom{n+k-1}{k}(-x)^k \\ &= \sum_{k=0}^\infty\binom{n+k-1}{k}x^k. \\ \end{align*} :::warning $\frac{1}{(1-x)^n} =(1-x)^{-n}$ generates $\binom{n-1}{0}, \binom{n}{1}, \binom{n+1}{2},\cdots,\binom{n+k-1}{k},\cdots$ for $n\gt 0$. ::: ## Differencing Using multiplication (by a constant or by $y=h(x)$), substitution, addition, and differentiation, we may produce a wide variety of generating functions. Another elegant way for finding generating functions is to find the sequence of differences between terms of a sequence. The sequence of differences is often simpler than the original sequence. So if we know a generating function for the differences, we would like to use this to find a generating function for the original sequence. #### ex. Find a generating function for $1,3, 5, 7, 9, \cdots$ Notice that the differences between consecutive terms in the sequence are constant. Let $A=1+3x+5x^2+7x^3+9x^4+ \cdots.$ \begin{aligned} A&=1+3x+5x^2+7x^3+9x^4+ \cdots \\ \underline{x\ A}&\underline{\,\, = ~~~~~~~~~ x + 3x^2 + 5x^3 + 7x^4 + \cdots} \\ (1-x)A&=1+2x+2x^2+2x^3+2x^4+ \cdots \\ &=1+2x(1+x+x^2+x^3+x^4+ \cdots) \\ &=1+\frac{2x}{1-x} \\ A&=\frac{1}{1-x}+\frac{2x}{(1-x)^2}=\frac{1+x}{(1-x)^2} \end{aligned} Note that $\frac{1}{1-x}$ generates $1, 1, 1, 1, \cdots$ and $\frac{1}{(1-x)^2}$ generates $1,2,3,4,5,\cdots$ so that $\frac{2x}{(1-x)^2}$ generates $0,2,4,6,8,\cdots$. Adding $1, 1, 1, 1, \cdots$ and $0,2,4,6,8,\cdots$ gives $1,3, 5, 7, 9, \cdots$. The equality is preserved by incorporating their respective generating functions similarly. #### ex. Find the generating function for $1, 4, 9, 16, 25,\cdots$. \begin{aligned} A&=1+4x+9x^2+16x^3+25x^4+ \cdots \\ \underline{x\ A}&\underline{\,\, = ~~~~~~~~ x + ~4x^2 +\ 9x^3 + 16x^4 + \cdots} \\ (1-x)A&=1+3x+~5x^2+~7x^3+~9x^4+ \cdots \\ &=\frac{1+x}{(1-x)^2} \\ A&=\frac{1+x}{(1-x)^3} \end{aligned} Note that $1, 4, 9, 16, 25,\cdots$ is the prefix-sum series of $1, 3, 5, 7, 9,\cdots$ and $\frac{1}{1-x}$ is the summation operator. From the avobe examples, we realize that the differences between consecutive terms in $S$ produce another series $S'$ whose generating function $G(x)'$ has been found, from which we could find the generating function $G(x)$ for $S$. The concept of defferencing can be generalized to explore more complicated relationships between terms of the sequence. Suppose that a sequence satisfies the recurrence relation $a_n=3a_{n-1}-2a_{n-2}$. That means $a_n-3a_{n-1}+2a_{n-2}=0$, which holds for all but the first two terms of the sequence. We may determine the generating function such a series. #### ex. Find the generating function for sequence $1, 3, 7, 15, \cdots$, which satisfies $a_n-3a_{n-1}+2a_{n-2}=0$. Let $A$ be $\{a_n\}_0^\infty$ \begin{aligned} A&=1+3x+7x^2+15x^3+31x^4+ \cdots+~a_nx^n+\cdots \\ -3x\ A&{\,\, = 0 -3x -9x^2 -21x^3 -45x^4 + \cdots-3a_nx^n+\cdots} \\ \underline{+2x^2\ A}&\underline{\,\, = 0 +0x+2x^2+~6x^3+14x^4 + \cdots+2a_nx^n+\cdots} \\ (1-3x+2x^2)A&=1\\ A&=\frac{1}{(1-3x+2x^2)} \end{aligned} #### ex. Find the generating function for sequence $0, 1, 1, 2, 3, 5, 8, \cdots$, which satisfies $f_n=f_{n-1}+f_{n-2}$ (i.e., Fibonacci sequence). Let $F$ be $\{f_n\}_0^\infty$. \begin{aligned} F&=0+1x+1x^2+2x^3+3x^4+5x^5+8x^6\cdots \\ -x\ F&{\,\, = 0-0x -1x^2 -1x^3 -2x^4 -3x^5-5x^6 - \cdots} \\ \underline{-x^2\ F}&\underline{\,\, = 0-0x-0x^2-1x^3-1x^4-2x^5-3x^6-\cdots} \\ (1-x-x^2)F&=~~~~~~~~ x\\ F&=\frac{x}{(1-x-x^2)} \end{aligned} ## Multiplication and Partial/Prefix Sums Consider $A=a_0+a_1x+a_2x^2+\cdots$ and $B=b_0+b_1x+b_2x^2+\cdots$. :::success $AB=a_0b_0+(a_0b_1+a_1b_0)x+(a_0b_2+a_1b_1+a_2b_0)x^2+(a_0b_3+a_1b_2+a_2b_1+a_3b_0)x^3+\cdots$ ::: #### ex. Find the generating function for $AB: 1,4,11,28,57, \cdots$ where $A: 1, 2, 3, 4,5,\cdots$ and $B: 1, 2,4, 8, 16,\cdots$ Since $G_A(x) = \dfrac{1}{(1-x)^2}$ and $G_B(x) = \dfrac{1}{1-2x}$, $G_{AB}(x) = G_A(x)G_B(x)=\dfrac{1}{(1-x)^2(1-2x)}$. #### ex. Given $A: 1, 1, 1, 1,1,\cdots$ and $B: 1, 2,3,4,5,\cdots$Find the generating function for $AB$. \begin{aligned} A&=1+x+x^2+x^3+x^4+x^5+\cdots \\ \underline{~B}&\underline{\,\, = 1+2x+3x^2+4x^3+5x^4+ \cdots ~~~~~ } \\ &~~~~~~ 1+~x+~x^2+~~ x^3+~~ x^4+~~ x^5+\cdots\\ &~~~~~~~~~~~ 2x+2x^2+2x^3+2x^4+2x^5+\cdots\\ &~~~~~~~~~~~~~~~~~~~~ 3x^2+3x^3+3x^4+3x^5+\cdots\\ &~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 4x^3+4x^4+4x^5+4x^6+\cdots \\ &\underline{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \cdots ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ } \\ AB&= 1+3x+6x^2+10x^3+15x^4+21x^5+\cdots \end{aligned} $AB$ is the *triangular numbers*. More precisely, it is the prefix-sum of $B$. We may compute the generating function of $AB$ by \begin{aligned} G_{AB}(x)&=G_{A}(x)G_{B}(x) \\ &=\frac{1}{1-x}\frac{1}{(1-x)^2} \\ &=\frac{1}{(1-x)^3} \end{aligned} Recall that $\frac{1}{1-x}$ is the prefix/partial-sum operator. Table 1 summarizes the features of $\frac{1}{1-x}$ and $(1-x)$ in the scope of generating functions. <div style="display: grid; justify-content: center; align-content: center;"> | Generating function | $G(x)$ | $(1-x)G(x)$ | $\dfrac{1}{1-x}G(x)~~(=(1-x)^{-1}G(x))$ | |:--------:|:--------:| :--------: | :--------: | |Expanded form | $A$ | $A-xA\ (\text{difference of }A)$ | $\text{prefix-sum of }A$ | </div> ## Solving Recurrence Relations with Generating Functions #### ex. Solve the recurrence relation $a_n-3a_{n-1}+2a_{n-2}$ with $a_0=1$ and $a_1=3$. As mentioned above, this recurrence relation gives the sequence $1, 3, 7, 15, 31, 63,\cdots$ which has generating function $\frac{1}{1-3x+x^2}$. Further, $\qquad\qquad \dfrac{1}{1-3x+x^2} = \dfrac{1}{(1-x)(1-2x)}$ $\qquad\qquad\dfrac{1}{(1-x)(1-2x)}=\dfrac{a}{(1-x)}+\dfrac{b}{(1-2x)}=\dfrac{a(1 − 2x) + b(1 − x)}{(1-x)(1-2x)}.$ That is, $\qquad\qquad\ 1 = a(1 − 2x) + b(1 − x)$ must be true for all value of $x$. For $x=1$, we have $1=-a$, or $a=-1$. Regarding $x=\frac{1}{2}$, $1=\frac{b}{2}$, or $b=2$. As a result, $\qquad\qquad\dfrac{1}{(1-x)(1-2x)}=\dfrac{-1}{(1-x)}+\dfrac{2}{(1-2x)}.$ It is noticed that these two fractions are generating functions we know: $\qquad\qquad\dfrac{-1}{1-x}=-1-x-x^2-x^3-\cdots$ generates $-1, -1, -1, -1, \cdots$, which is $\{-1\}_0^{\infty}$; $\qquad\qquad\dfrac{2}{1-2x}=2+4x+8x^2+16x^3+32x^4+\cdots$ generates $2, 4, 8, 16, 32, \cdots$, which is $\{2^{n+1}\}_0^{\infty}$. Therefore, $\qquad\qquad\dfrac{1}{(1-x)(1-2x)}=\dfrac{-1}{(1-x)}+\dfrac{2}{(1-2x)}$ generates $1, 3, 7, 15, 31, 63,\cdots$, which is $\{2^{n+1}-1\}_0^{\infty}$. #### ex. Solve the recurrence relation $f_{n}=f_{n-1}+f_{n-2}$ with $f_0=0$ and $f_1=1$, which is the $n$th term of Fibonacci sequence. From the above example, we know that the generating function of Fibonacci seqeunce is $F(x)=\frac{x}{(1-x-x^2)}$. All that remains is to express this function as a power series. After doing so, we may match its coefficients term-by-term with the corresponding Fibonacci numbers. The roots of the polynomial ${(1-x-x^2)}(=-(x^2+x-1))$ are $-\frac{1+\sqrt 5}{2}$ and $-\frac{1-\sqrt 5}{2}$, denoted as $-\alpha$ and $-\beta$, respectively. Thus, the polynomial factors as $\qquad\qquad{(1-x-x^2)}=-(x^2+x-1)=-(x+\alpha)(x+\beta)$. In addition, $\alpha+\beta=1$, $\alpha-\beta=\sqrt 5$ and $\alpha\beta=-1$. In order to express the generating function as a power series, we will use the *partial fraction decomposition* to express it in the form $\qquad\qquad \dfrac{x}{(1-x-x^2)}=\dfrac{-x}{(x+\alpha)(x+\beta)}=\dfrac{a}{(x+\alpha)}+\dfrac{b}{(x+\beta)}$, which is equivalent to $\qquad\qquad −x=a(x+\beta)+b(x+\alpha),\text{ or }−x=(a+b)x+(a\beta+b\alpha)$. Letting $x=−\beta$, $\beta=b(-\beta+\alpha)(=b\sqrt 5)$ we have $b=\frac{\beta}{\sqrt 5}$, while $x=−\alpha$, $\alpha=a(-\alpha+\beta)(=-a\sqrt 5)$ we have $a=\frac{-\alpha}{\sqrt 5}$. As a result, $$F(x)=\dfrac{\frac{-\alpha}{\sqrt 5}}{(x+\alpha)}+\dfrac{\frac{\beta}{\sqrt 5}}{(x+\beta)}=\frac{1}{\sqrt 5}(\dfrac{\beta}{(x+\beta)}-\dfrac{\alpha}{(x+\alpha)}).$$ Note that using the following equations delivers the same result. \begin{cases} ~~a + b &= -1 \qquad(\Rightarrow \frac{-\alpha}{\sqrt 5}+\frac{\beta}{\sqrt 5}=\frac{\beta-\alpha}{\sqrt 5}=-1)\\ a\beta+b\alpha&=0 \qquad(\Rightarrow \frac{-\alpha}{\sqrt 5}\beta+\frac{\beta}{\sqrt 5}\alpha=\frac{-\alpha\beta+\alpha\beta}{\sqrt 5}=0)\\ \end{cases} We now wish to express each of these two terms in $F(x)$ as the sum of a geometric series. Owing to $\alpha\beta=-1$, $\dfrac{\beta}{x+\beta}=\dfrac{1}{1+\frac{x}{\beta}}=\dfrac{1}{1-\alpha x}=\displaystyle\sum_{k=0}^{\infty}\alpha^kx^k=\sum_{k=0}^{\infty}(\frac{1+\sqrt 5}{2})^kx^k$, $\dfrac{\alpha}{x+\alpha}=\dfrac{1}{1+\frac{x}{\alpha}}=\dfrac{1}{1-\beta x}=\displaystyle\sum_{k=0}^{\infty}\beta^kx^k=\sum_{k=0}^{\infty}(\frac{1-\sqrt 5}{2})^kx^k$. Therefore, \begin{aligned} F(x)&=\frac{1}{\sqrt 5}(\dfrac{\beta}{(x+\beta)}-\dfrac{\alpha}{(x+\alpha)})=\frac{1}{\sqrt 5}(\sum_{k=0}^{\infty}\alpha^kx^k-\sum_{k=0}^{\infty}\beta^kx^k)=\sum_{k=0}^{\infty}\frac{1}{\sqrt 5}(\alpha^k-\beta^k)x^k \\ &=\sum_{k=0}^{\infty}\frac{1}{\sqrt 5}[(\frac{1+\sqrt 5}{2})^k-(\frac{1-\sqrt 5}{2})^k]x^k \\ &=\sum_{k=0}^{\infty}f_kx^k. \end{aligned} Consequently, $$f_n=\frac{1}{\sqrt 5}[(\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n](=\frac{1}{\sqrt 5}(\alpha^n-\beta^n))$$ with $f_0=0$ and $f_1=1$. We give another simple yet tricky reduction as follows. \begin{aligned} \dfrac{x}{(1-x-x^2)}&=\dfrac{x}{(1-\alpha x)(1-\beta x)}\\ &=\dfrac{c}{(1-\alpha x)}+\dfrac{d}{(1-\beta x)} =\frac{c-c\beta x+d-d\alpha x}{(1-\alpha x)(1-\beta x)}\\ &=\frac{(c+d)-(d\alpha+c\beta)x}{(1-\alpha x)(1-\beta x)} \\ \end{aligned} Solving \begin{cases} ~~c + d &= 0 \qquad(\Rightarrow \frac{-\alpha}{\sqrt 5}+\frac{\beta}{\sqrt 5}=\frac{\beta-\alpha}{\sqrt 5}=-1)\\ d\alpha+c\beta&=-1 \qquad(\Rightarrow \frac{-\alpha}{\sqrt 5}\beta+\frac{\beta}{\sqrt 5}\alpha=\frac{-\alpha\beta+\alpha\beta}{\sqrt 5}=0),\\ \end{cases} we obtain $c=\frac{1}{\sqrt 5}$ and $d=\frac{-1}{\sqrt 5}$. Thus, \begin{aligned} \dfrac{x}{(1-x-x^2)}&=\dfrac{x}{(1-\alpha x)(1-\beta x)} =\dfrac{c}{(1-\alpha x)}+\dfrac{d}{(1-\beta x)}\\ &=\dfrac{\frac{1}{\sqrt 5}}{(1-\alpha x)}-\dfrac{\frac{1}{\sqrt 5}}{(1-\beta x)}=\frac{1}{\sqrt 5}(\dfrac{1}{1-\alpha x}-\dfrac{1}{1-\beta x}) \\ &=\frac{1}{\sqrt 5}(\sum_{k=0}^{\infty}\alpha^kx^k-\sum_{k=0}^{\infty}\beta^kx^k) \\ &=\sum_{k=0}^{\infty}\frac{1}{\sqrt 5}(\alpha^k-\beta^k)x^k \\ &=\sum_{k=0}^{\infty}\frac{1}{\sqrt 5}[(\frac{1+\sqrt 5}{2})^k-(\frac{1-\sqrt 5}{2})^k]x^k \\ &=\sum_{k=0}^{\infty}f_kx^k. \end{aligned} #### ex. [Vandermonde's convolution] Given $n, m\in \mathbb{N}$ and $r\in \mathbb{N}_0$, prove Vandermonde's equality: $\qquad\qquad \dbinom{n+m}{r}=\displaystyle\sum_{k=0}^r\binom{n}{k}\binom{m}{r-k}$ *proof* The generating function of sequence $\binom{n}{0}, \binom{n}{1}, \binom{n}{2},\cdots,\binom{n}{n}, 0, 0,,\cdots$ is $f(x)=(1+x)^n=\sum_{k=0}^n\binom{n}{k}x^k$, while that of $\binom{m}{0}, \binom{m}{1}, \binom{m}{2},\cdots,\binom{m}{m}, 0, 0,,\cdots$ is $g(x)=(1+x)^m=\sum_{k=0}^m\binom{m}{k}x^k$. $\qquad f(x)g(x)=\binom{n}{0}\binom{m}{0}+[\binom{n}{0}\binom{m}{1}+\binom{n}{1}\binom{m}{0}]x+[\binom{n}{0}\binom{m}{2}+\binom{n}{1}\binom{m}{1}+\binom{n}{2}\binom{m}{0}]x^2+\cdots$ $\qquad\qquad\qquad=(1+x)^n(1+x)^m = (1+x)^{n+m}$. The coefficient at term $x^r$ in $f(x)g(x)$ is $\qquad \binom{n}{0}\binom{m}{r}+\binom{n}{1}\binom{m}{r-1}+\binom{n}{2}\binom{m}{r-2}+\cdots+\binom{n}{r}\binom{m}{0}=\displaystyle\sum_{k=0}^r\binom{n}{k}\binom{m}{r-k}.$ https://austinrochford.com/posts/2013-11-01-generating-functions-and-fibonacci-numbers.html --- # [作業四] ### 1. Find the generating function for each of the following sequences by relating them back to a sequence with known generating function. $(a)\ 4,4,4,4,4,......$ $(b)\ 2,4,6,8,10,......$ $(c)\ 0,0,0,2,4,6,8,10,......$ $(d)\ 1,5,25,125,......$ $(e)\ 1,-3,9,-27,81,......$ $(f)\ 1,0,5,0,25,0,125,0,......$ $(g)\ 0,1,0,0,2,0,0,3,0,0,4,0,0,5,......$ :::spoiler 中文將以下每個數列與已知生成函數相關聯，找到它們的生成函數。 ::: :::spoiler 解答 $(a)\ A(x)=\dfrac{4}{1-x}$ $(b)\ B(x)=\dfrac{2}{(1-x)^2}$ $(c)\ C(x)=x^3\dfrac{2}{(1-x)^2}$ $(d)\ D(x)=\dfrac{1}{1-5x}$ $(e)\ E(x)=\dfrac{1}{1+3x}$ $(f)\ F(x)=\dfrac{1}{1-5x^2}$ $(g)\ G(x)=\dfrac{x}{(1-x^3)^2}$ ::: :::spoiler 詳解 $(a)$ $\begin{aligned}&A(x)=1+x+x^2+x^3+...=\dfrac{1}{1-x}\\&4A(x)=4+4x+4x^2+4x^3+...=\dfrac{4}{1-x}\end{aligned}$ $(b)$ $\begin{aligned}B'(x)&=1+2x+3x^2+4x^3+5x^4+...\\xB'(x)&=x+2x^2+3x^3+4x^4+5x^5+...\\ \hline (1-x)B'(x)&=1+x+x^2+x^3+x^4+x^5+...\\(1-x)B'(x)&=\dfrac{1}{1-x}\\B(x)&=2B'(x)=\dfrac{2}{(1-x)^2}\end{aligned}$ $(d)$ $\begin{aligned}D(x) = 1+5x+(5x)^2+(5x)^3+...=\dfrac{1}{1-(5x)}\end{aligned}$ $(e)$ $\begin{aligned}E(x) = 1+(-3x)x+(-3x)^2+(-3x)^3+...=\dfrac{1}{1-(-3x)}=\dfrac{1}{1+3x}\end{aligned}$ $(f)$ 令$5x^2=Z$ $\begin{aligned}F(x) = 1+5x^2+25x^4+125x^6+...&=1+5x^2(1+5x^2+25x^4+125x^6+...) \\&=1+Z(1+Z+Z^2+Z^3+...) \\&=1+Z\dfrac{1}{1-Z} \\&=\dfrac{1-Z+Z}{1-Z} \\&=\dfrac{1}{1-Z} \\&=\dfrac{1}{1-5x^2}\end{aligned}$ $(g)$ 令$x^3=Z$ $\begin{aligned}G(x) = x+2x^4+3x^7+4x^{10}+5x^{13}+...&=x(1+2x^3+3x^6+4x^{9}+5x^{12}+...) \\&=x(1+2Z+3Z^2+4Z^3+5Z^4...) \\&=x\dfrac{1}{(1-Z)^2} \\&=\dfrac{x}{(1-x^3)^2} \end{aligned}$ ::: ### 2. Find the sequence generated by the following generating functions: $(a)\ \dfrac{4x}{1-x}$ $(b)\ \dfrac{1}{1-4x}$ $(c)\ \dfrac{x}{1+x}$ $(d)\ \dfrac{3x}{(1+x)^2}$ $(e)\ \dfrac{1+x+x^2}{(1-x)^2}$(Hint: multiplication). :::spoiler 中文求下列生成函數所產生的數列： ::: :::spoiler 解答 $(a)\ 0,4,4,4,4,4,...$ $(b)\ 1,4,16,64,256,...$ $(c)\ 0,1,−1,1,−1,1,−1,...$ $(d)\ 0,3,−6,9,−12,15,−18,...$ $(e)\ 1,3,6,9,12,15,...$ ::: :::spoiler 詳解 $(a)$ $\begin{aligned}\dfrac{4x}{1-x}=4x(\dfrac{1}{1-x})=4x(1+x+x^2+x^3+...)&=4x+4x^2+4x^3+4x^4+...\\&\implies 0,4,4,4,4,...\end{aligned}$ $(b)$ $\begin{aligned}\dfrac{1}{1-4x}=1+(4x)+(4x)^2+(4x)^3+...&=1+4x+16x^2+64x^3+...\\&\implies1,4,16,64,256,...\end{aligned}$ $(c)$ $\begin{aligned}\dfrac{x}{1+x}&=x(1+(-x)+(-x)^2+(-x)^3+(-x)^4+...) \\&=x(1-x+x^2-x^3+x^4+...) \\&=x-x^2+x^3-x^4+... \\&\implies0,1,-1,1,-1,1,...\end{aligned}$ $(d)$ $\begin{aligned}\dfrac{3x}{(1+x)^2}&=3x\dfrac{1}{(1-(-x))^2} \\&=3x(1+2(-x)+3(-x)^2+4(-x)^3+5(-x)^4+...) \\&=3x(1-2x+3x^2-4x^3+5x^4+...) \\&=3x-6x^2+9x^3-12x^4+15x^5+...) \\&\implies0,3,-6,9,-12,15,-18,...\end{aligned}$ $(e)$ $\begin{aligned}\dfrac{1+x+x^2}{(1-x)^2}=(1+x+x^2)(1+2x+3x^2+&4x^3+5x^4+...) \\x+2x^2+&3x^3+4x^4+... \\x^2+&2x^3+3x^4+... \\\hline \dfrac{(1+x+x^2)(1-x)}{((1-x)^2)(1-x)}=1+3x+6x^2+&9x^3+12x^4+15x^5+... \\\implies1,3,6,9,12,&15,...\end{aligned}$ ::: ### 3. Show how you can get the generating function for the triangular numbers in three different ways: :::info Triangular numbers : $1,3,6,10,15,...$ ::: $a.$ Take two derivatives of the generating function for $1,1,1,1,1,...$ $b.$ Use differencing. $c.$ Multiply two known generating functions. :::spoiler 中文用三種不同的方式求Triangular numbers的生成函數： ::: :::spoiler 詳解 $(a)$ $\begin{aligned}\dfrac{1}{1-x}&=1+x+x^2+x^3+... \\\dfrac{d}{dx}(1-x)^{-1}&=-1(1-x)^{-2}\cdot(-1)=\dfrac{1}{(1-x)^2}=0+1+2x+3x^2+4x^3+... \\\dfrac{d}{dx}(1-x)^{-2}&=-2(1-x)^{-3}\cdot(-1)=\dfrac{1}{(1-x)^3}=0+2+6x+12x^2+20x^3+... \\&\overset{\div2}{\implies}1+3x+6x^2+10x^3+... \\\end{aligned}$ $\dfrac{1}{(1-x)^3}$ generate $1,3,6,10,15,...$ $(b)$ $\begin{aligned}令\ G(x)&=1+3x+6x^2+10x^3+15x^4+...為g.f. \\-xG(x)&=0+\ \ x+3x^2+\ \ 6x^3+10x^4+... \\\hline (1-x)G(x)&=1+2x+3x^2+\ \ 4x^3+\ \ 5x^4+... \\即(1-x)G(x)&=\dfrac{1}{(1-x)^2}\implies G(x)=\dfrac{1}{(1-x)^3}\end{aligned}$ $(c)$ 執行prefix sum of $1,2,3,4,...$ 可得 $1,3,6,10,15,...$ 前者$g.f.$為$\dfrac{1}{(1-x)^2}$，欲得prefix sum 可乘 $\dfrac{1}{1-x}$ 後者$g.f.$為$\dfrac{1}{(1-x)^3}$ ::: ### 4. Use differencing to find the generating function for $4,5,7,10,14,19,25,...$ :::spoiler 詳解 $\begin{aligned}令\ G(x)&=4+5x+7x^2+10x^3+14x^4+19x^5+... \\-xG(x)&=0+4x+5x^2+\ \ 7x^3+10x^4+14x^5+... \\\hline (1-x)G(x)&=4+\ \ x+2x^2+\ \ 3x^3+\ \ 4x^4+\ \ 5x^5+... \\&=4+x(1+2x+3x^2+4x^3+5x^4) \\&=4+\dfrac{x}{(1-x)^2} \\&=\dfrac{4-8x+x^2+x}{(1-x)^2}\end{aligned}$ $\begin{aligned}故\ G(x)&=\dfrac{4+\dfrac{x}{(1-x)^2}}{1-x} \\&=\dfrac{4}{1-x}+\dfrac{x}{(1-x)^3} \\&=(4+4x+4x^2+4x^3+...)+(x+3x^2+6x^3+10x^4+...) \\&=4+5x+7x^2+10x^3+...\end{aligned}$ ::: ### 5. Find a generating function for the sequence with recurrence relation $a_n=3a_{n-1}-a_{n-2}$ with initial terms $a_0=1$ and $a_1=5$. :::spoiler 解答 $\dfrac{1+2x}{1-3x+x^2}$ ::: :::spoiler 詳解令$a_0,a_1,a_2,a_3,...$的$g.f.$為$g(x)=a_0+a_1x+a_2x^2+a_3x^3+...$ $\begin{aligned} g(x)&=a_0+a_1x+\ \ a_2x^2+\ \ a_3x^3+... \\-3xg(x)&=\ \ \ \ \ \ \ 3a_0x+3a_1x^2+3a_2x^3+... \\+x^2g(x)&=\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ a_0x^2+\ \ a_1x^3+... \\\hline g(x)-3xg(x)+x^2g(x)&=a_0+(a_1-3a_0)x+(a_2-3a_1+a_0)x^2+...\end{aligned}$ $\begin{aligned}&g(x)(1-3x+x^2)=1+2x \\&g(x)=\dfrac{1+2x}{1-3x+x^2}\end{aligned}$ ::: ### 6. Use the recurrence relation for the Fibonacci numbers to find the generating function for the Fibonacci sequence. :::spoiler 解答 $\dfrac{x}{1-x-x^2}$ ::: :::spoiler 詳解 $F_n=F_{n-1}+F_{n-2},\ F_0=0,\ F_1=1$ 令$0,1,1,2,3,5,8,...$的$g.f.$為$f(x)=0+x+x^2+2x^3+3x^4+...$ $\begin{aligned}f(x)&=x+x^2+2x^3+3x^4+5x^5+8x^6+... \\-xf(x)&=\quad\ \ \ x^2+\ \ x^3+2x^4+3x^5+5x^6+... \\-x^2f(x)&=\quad\quad\quad\quad\ \ x^3+\ \ x^4+2x^5+3x^6+... \\\hline f(x)-xf(x)-x^2f(x)&=x\\ f(x)(1-x-x^2)&=x \\f(x)&=\dfrac{x}{1-x-x^2}\end{aligned}$ ::: ### 7. Use multiplication to find the generating function for the sequence of partial sums of Fibonacci numbers, $S_0,S_1,S_2,...$ where $S_0=F_0,\ S_1=F_0+F_1,\ S_2=F_0+F_1+F_2,\ S_3=F_0+F_1+F_2+F_3$ and so on. :::spoiler 解答 $\dfrac{x}{(1-x)(1-x-x^2)}$ ::: :::spoiler 詳解 $f(x) = \dfrac{x}{1-x-x^2}$ $\dfrac{1}{1-x}f(x)$ 可得 $f(x)$ 之 prefix sum: $\dfrac{1}{1-x}f(x) = \dfrac{x}{(1-x)(1-x-x^2)}$ ::: ### 8. Find the generating function for the sequence with closed formula $a_n=2(5^n)+7(-3)^n$. :::spoiler 解答 $\dfrac{2}{1-5x}+\dfrac{7}{1+3x}$ ::: :::spoiler 詳解令$5^0,5^1,5^2,5^3,5^4,5^5,...$的$g.f.$為$\alpha (x)=5^0+5x+(5x)^2+(5x)^3+(5x)^4+...$ 令$Z=5x$，$\alpha (x)=1+Z+Z^2+Z^3+Z^4+...=\dfrac{1}{1-Z}\implies\alpha (x)=\dfrac{1}{1-5x}$ 令$-3^0,(-3)^1,(-3)^2,(-3)^3,(-3)^4,(-3)^5,...$的$g.f.$為$\beta (x)=(-3)^0+(-3)x+(-3x)^2+(-3x)^3+(-3x)^4+...$ 令$Z=-3x$，$\beta (x)=1+Z+Z^2+Z^3+Z^4+...=\dfrac{1}{1-Z}\implies\beta (x)=\dfrac{1}{1+3x}$ $r(x)=2\alpha(x)+7\beta(x)=\dfrac{2}{1-5x}+\dfrac{7}{1+3x}$ ::: ### 9. Find a closed formula for the $n$th term of the sequence with generating function $\dfrac{3x}{1-4x}+\dfrac{1}{1-x}$ :::spoiler 解答 $a_n=3\cdot 4^{n-1}+1$ ::: :::spoiler 詳解 $\begin{aligned}\dfrac{3x}{1-4x}+\dfrac{1}{1-x}&=3x(1+4x+(4x)^2+(4x)^3+...)+(1+x+x^2+x^3+...) \\&=3(x+...+x(4x)^{n-1}+...)+(1+...+x^n+...) \end{aligned}$ 其為 $x^n$ 項係數：$3\cdot 4^{n-1}x^n+x^n\implies(3\cdot 4^{n-1}+1)x^n$ $a_n=3\cdot 4^{n-1}+1$ ::: ### 10. Find $a_7$ for the sequence with generating function $\dfrac{2}{(1-x)^2} \cdot \dfrac{x}{1-x-x^2}$ :::spoiler 解答 $158$ ::: :::spoiler 詳解 $\begin{aligned}\dfrac{2}{(1-x)^2} \cdot \dfrac{x}{1-x-x^2}=[2(1+2x+3x^2+4x^3+...)][0+x+x^2+2x^3+3x^4+5x^5+8x^6+...] \end{aligned}$ $\begin{aligned}1\quad 2\quad 3\quad 4\quad 5 \quad 6 \quad 7 \quad &8 \\0\quad1\quad1\quad2\quad3\quad5\quad8\quad&13 \\\end{aligned}$ $[(8\times0)+(7\times1)+(6\times1)+(5\times2)+(4\times3)+(3\times5)+(2\times8)+(1\times13)]\times2 = 158$ ::: ### 11. Explain how we know that $\dfrac{1}{(1-x)^2}$ is the generating function for $1,2,3,4,,...$ . :::spoiler 詳解 $\begin{aligned}\dfrac{1}{(1-x)}\cdot\dfrac{1}{(1-x)}&=(1+x+x^2+x^3+...)(1+x+x^2+x^3+...) \\&=1+(1\cdot1+1\cdot1)x+(1\cdot1+1\cdot1+1\cdot1)x^2+...+\underbrace{(1\cdot1+1\cdot1+...+1\cdot1)}_\text{k}x^k \\&=1+2x+3x^2+4x^3+5x^4+... \\\\\dfrac{1}{(1-x)}&=1+x+x^2+x^3+... \\\dfrac{d}{dx}\dfrac{1}{(1-x)}&=\dfrac{d}{dx}(1-x)^{-1}=-(1-x)^{-2}(-1)=\dfrac{1}{(1-x)^2}\\\dfrac{d}{dx}(1+x+x^2+x^3+...)&=0+1+2x+3x^2+4x^3+5x^4+...\\\\ \therefore \ \dfrac{1}{(1-x)^2}&=1+2x+3x^2+4x^3+5x^4+...\end{aligned}$ ::: ### 12. Starting with the generating function for $1,2,3,4,,...$ , find a generating function for each of the following sequences. $(a)\ 1, 0, 2, 0, 3, 0, 4,...$ $(b)\ 1,−2, 3,−4, 5,−6,...$ $(c)\ 0, 3, 6, 9, 12, 15, 18,...$ $(d)\ 0, 3, 9, 18, 30, 45, 63,...$(Hint: relate this sequence to the previous one.) :::spoiler 解答 $(a)\ \dfrac{1}{(1-x^2)^2}$ $(b)\ \dfrac{1}{(1+x)^2}$ $(c)\ \dfrac{3x}{(1-x)^2}$ $(d)\ \dfrac{3x}{(1-x)^3}$(partial sums). ::: :::spoiler 詳解 $\begin{aligned}A(x)=\dfrac{1}{(1-x)^2}=1+2x+3x^2+4x^3+5x^4+...\end{aligned}$ $(a)$ $\begin{aligned} \\a(x)&=1+2x^2+3x^4+4x^6+5x^8+... \\\\令x^2&=Z\\ a(x)&=1+2Z+3Z^2+4Z^3+5Z^4+...=\dfrac{1}{(1-Z)^2}=\dfrac{1}{(1-x^2)^2}\end{aligned}$ $(b)$ $\begin{aligned} \\\alpha(x)&=1+2x+3x^2+4x^3+5x^4+...=\dfrac{1}{(1-x)^2} \\\\令x&=-y\\ \alpha(x)&=1+2(-y)+3(-y)^2+4(-y)^3+5(-y)^4+... \\&=1-2y+3y^2-4y^3+5y^4-...=\dfrac{1}{(1-(-y))^2}=\dfrac{1}{(1+y)^2} \\\\所求\ &b(x)=1-2x+3x^2-4x^3+5x^4-...=\dfrac{1}{(1+x)^2}\end{aligned}$ $(c)$ $\begin{aligned} &0, 3, 6, 9, 12, 15, 18,...\overset{ \div3}{\implies}0,1,2,3,4,5,6,... \\&0,1,2,3,4,5,6,...\implies x\alpha(x)=0+x+2x^2+3x^3+...=\dfrac{1}{(1-x)^2} \\&0, 3, 6, 9, 12, 15, 18,...\implies 3x\alpha(x)=\dfrac{3x}{(1-x)^2} \end{aligned}$ $(d)$ $\begin{aligned} &0, 3, 9, 18, 30, 45, 63,...\overset{ \div3}{\implies}0,1,3,6,10,15,21... \\&0,1,3,6,10,15,21...\implies \text{Triangular numbers} =\dfrac{x}{(1-x)^3} \\&0, 3, 6, 9, 12, 15, 18,...\implies \dfrac{3x}{(1-x)^3} \end{aligned}$ ::: ### 13. You may assume that $1,1,2,3,5,8,...$ has generating function $\dfrac{1}{1-x-x^2}$(because it does). Use this fact to find the sequence generated by each of the following generating functions. $(a)\ \dfrac{x^2}{1-x-x^2}$ $(b)\ \dfrac{1}{1-x^2-x^4}$ $(c)\ \dfrac{1}{1-3x-9x^2}$ $(d)\ \dfrac{1}{(1-x-x^2)(1-x)}$ :::spoiler 解答 $(a)\ 0,0,1,1,2,3,5,8,...$ $(b)\ 1,0,1,0,2,0,3,0,5,0,8,0,...$ $(c)\ 1,3,18,81,405,...$ $(d)\ 1,2,4,7,12,20,...$ ::: :::spoiler 詳解 $1,1,2,3,5,8$ with $g.f.\dfrac{1}{1-x-x^2}$ $(a)\dfrac{x^2}{1-x-x^2}=x^2+x^3+2x^4+3x^5+5x^6+8x^7+...\implies0,0,1,1,2,3,5,8,...$ $\begin{aligned}(b)\dfrac{1}{1-x^2-x^4}\ 令Z=x^2\end{aligned}$ $\begin{aligned}\dfrac{1}{1-Z-Z^2}&= 1+Z+2Z^2+3Z^3+5Z^4+8Z^5+...\\&=1+x^2+2x^4+3x^6+5x^8+8x^{10}+...\\\\&\implies 1,0,1,0,2,0,3,0,5,0,8,0,...\end{aligned}$ $(c)\dfrac{1}{1-3x-9x^2}$ 令$Z=3x$ $\begin{aligned}\dfrac{1}{1-Z-Z^2}&=1+Z+2Z^2+3Z^3+5Z^4+...\\&=1+3x+2\cdot9x^2+3\cdot27x^3+5\cdot3^4x^4+...\\\\&\implies1,3,18,81,405,...\end{aligned}$ $\begin{aligned}(d)\dfrac{1}{(1-x-x^2)(1-x)}&=\dfrac{1}{1-x-x^2}\cdot\dfrac{1}{1-x}\\&=(1+x+2x^2+3x^3+5x^4+8x^5+...)(1+x+x^2+...)\\&=1+2x+(1\cdot1+1\cdot1+2\cdot1+...)x^2+(1\cdot1+1\cdot1+2\cdot1+3\cdot1)x^3+(1\cdot1+1\cdot1+2\cdot1+3\cdot1+5\cdot1)x^4...\\&=1+2x+4x^2+7x^3+12x^4+...\\\\&\implies1,2,4,7,12,20,...\end{aligned}$ ::: ### 14. Find the generating function for the sequence $1,-2,4,-8,16,...$ :::spoiler 解答 $\dfrac{1}{1+2x}$ ::: :::spoiler 詳解 $\begin{aligned}&1,-2,4,-8,16,...=(-2)^0+(-2)^1+(-2)^2+(-2)^3+(-2)^4+...=\sum_{i=0}^{\infty}(-2)^i\\&1+(-2)x+(2x)^2+(-2x)^3+(2x)^4+...=\dfrac{1}{1+2x}\end{aligned}$ ::: ### 15. Find the generating function for the sequence $1,1,1,2,3,4,5,6,...$ :::spoiler 解答 $\dfrac{x^3}{(1-x)^2}+\dfrac{1}{1-x}$ ::: :::spoiler 詳解 $\alpha (x)=1+x$ $\begin{aligned}\beta (x)&=x^2+2x^3+3x^4+4x^5+5x^6+... \\&=x^2(1+2x+3x^2+4x^3+5x^4+...) \\&=x^2(\dfrac{1}{(1-x)^2})\end{aligned}$ $\begin{aligned}\alpha (x)+\beta (x)&=1+x+\dfrac{x^2}{(1-x)^2} \\&=\dfrac{(1+x)(1-2x+x^2)+x^2}{(1-x)^2} \\&=\dfrac{1-2x+x^2+x-2x^2+x^3+x^2}{(1-x)^2} \\&=\dfrac{1-x+x^3}{(1-x)^2} \\&=\dfrac{1-x}{(1-x)^2}+\dfrac{x^3}{(1-x)^2} \\&=\dfrac{1}{1-x}+\dfrac{x^3}{(1-x)^2}\end{aligned}$ ::: ### 16. Suppose $A$ is the generating function for the sequence $3,5,9,15,23,33,...$ $(a)$ Find a generating function (in terms of $A$) for the sequence of differences between terms. $(b)$ Write the sequence of differences between terms and find a generatingfunction for it (without referencing $A$). $(c)$ Use your answers to parts (a) and (b) to find the generating function forthe original sequence. :::spoiler 解答 $(a)\ \ (1-x)A=3+2x+4x^2+6x^3+...$which is almostright.We can fix it like this:$2+4x+6x^2+...=\dfrac{(1-x)A-3}{x}$ $(b)$ We know $2+4x+6x^2+...=\dfrac{2}{(1-x)^2}$ $(c)\ \ A=\dfrac{3}{(1-x)}+\dfrac{2x}{(1-x)^3}$ ::: :::spoiler 詳解 $\begin{aligned}x^0\ &x^1\ x^2\ x^3\ x^4\ x^5 \\A(x)=3,\ &5,\ 9,15,23,33,... \\xA(x)=\quad\ &3,\ 5,\ \ 9,15,23,... \\(1-x)A(x)=3,\ &2,\ 4,\ \ 6,\ \ 8,10,...\\=3+&2x(1+2x+3x^2+4x^3+5x^4+...)\end{aligned}$ $(1-x)A(x)=3+2x\dfrac{1}{(1-x)^2}$ $A(x)=\dfrac{3+\dfrac{2x}{(1-x)^2}}{(1-x)} =\dfrac{3}{(1-x)}+\dfrac{2x}{(1-x)^3}$ ::: --- ### 17. $證明\ rf(x)+sg(x)\ 為\ \{ra_n+sb_n\}_0^\infty\ 的生成函數$ :::spoiler solution 直接計算得\ $rf(x)+sg(x)=r\begin{aligned}\sum_{n=0}^{\infty}a_nx^n+s\sum_{n=0}^{\infty}b_nx^n=\sum_{n=0}^{\infty}(ra_n+sb_n)x^n\end{aligned}$，所以$\ rf(x)+sg(x)\ 為\ \{ra_n+sb_n\}_0^\infty\ 的生成函數$ ::: ### 18. $證明對於正整數h，x^hf(x)為\underbrace{0,0,...,0}_\text{h個},a_0,a_1,...的生成函數$ :::spoiler solution $x^hf(x)=x^h\begin{aligned}\sum_{n=0}^{\infty}a_nx^n=\sum_{n=h}^{\infty}a_{n-h}x^n\end{aligned}，x^hf(x)為\underbrace{0,0,...,0}_\text{h個},a_0,a_1,...的生成函數$ ::: ### 19. $證明對於正整數h，\dfrac{f(x)-a_0-...-a_{h-1}x^{h-1}}{x^h}為a_h,a_{h+1},...的生成函數$ :::spoiler solution $\begin{aligned}\sum_{n \ge0}^{}a_{n+1}x^n=\dfrac{1}{x}\sum_{m \ge1}^{}a_{m}x^m=\dfrac{f(x)-f(0))}{x}=\dfrac{f(x)-a_0}{x}\end{aligned}$ 所以 $\dfrac{f(x)-a_0}{x}$ 為 $\{a_{n+1}\}_0^\infty\ 的生成函數$ $\begin{aligned}\sum_{n \ge0}^{}a_{n+2}x^n=\dfrac{1}{x}\sum_{n+1\ge1}^{}a_{n+1}x^n=\dfrac{[(f(x)-a_0)/x]-a_1}{x}=\dfrac{f(x)-a_0-a_1x}{x^2}\end{aligned}$ 所以 $\dfrac{f(x)-a_0-a_1x}{x^2}$ 為 $\{a_{n+2}\}_0^\infty\ 的生成函數$ 同理，$\dfrac{f(x)-a_0-...-a_{h-1}x^{h-1}}{x^h}為\{a_{n+h}\}_0^\infty\ 的生成函數$ ::: ### 20. $證明f(x)g(x)為\{\begin{aligned}\sum_{r=0}^{n}a_rb_{n-r}\end{aligned}\}_0^\infty的生成函數$ ::: spoiler solution 由冪級數的乘法規則得 $\begin{aligned}f(x)g(x)&=(a_0+a_1x+a_2x^2+...)(b_0+b_1x+b_2x^2+...)\\&=a_0b_0+(a_0b_1+a_1b_0)x+(a_0b_2+a_1b_1+a_2b_0)x^2+...\\&=\sum_{n=0}^{\infty}(a_0b_n+a_1b_{n-1}+...+a_{n-1}b_1+a_nb_0)x^n\end{aligned}$ 所以 $f(x)g(x)為\{\begin{aligned}\sum_{r=0}^{n}a_rb_{n-r}\end{aligned}\}_0^\infty的生成函數$ ::: ### 21. $證明f(cx)為\{c^na_n\}_0^\infty的生成函數$ :::spoiler solution $f(x)=\begin{aligned}\sum_{n=0}^{\infty}a_nx^n\end{aligned}$ ，則 $f(cx)=\begin{aligned}\sum_{n=0}^{\infty}a_n(cx)^n\end{aligned}$ 因此，$f(cx)為\{c^na_n\}_0^\infty的生成函數$ ::: ### 22. $證明f'(x)為\{(n+1)a_{n+1}\}_0^\infty的生成函數$ :::spoiler solution $f(x)=\begin{aligned}\sum_{n=0}^{\infty}a_nx^n\end{aligned}$ ，兩邊對$x$微分得 $f'(x)=\begin{aligned}\sum_{n=1}^{\infty}na_nx^{n-1}\end{aligned}$ 則 $f'(x)\ 是\ a_1,2a_2,3a_3,...=\{(n+1)a_{n+1}\}_0^\infty的生成函數$ ::: ### 23. $證明\int_0^x f(t) \mathrm{d} t為\{\dfrac{a_{n-1}}{n}\}_0^\infty的生成函數$ :::spoiler solution 計算得 \begin{aligned}\int_0^x f(t) \mathrm{d} t=\int_0^x f(t) \sum_{n=0}^{\infty}a_nt^n\mathrm{d} t=\sum_{n=0}^{\infty}a_n(\int_0^x t^n \mathrm{d} t)=\sum_{n=1}^{\infty}\dfrac{a_{n-1}}{n}x^n=\{\dfrac{a_{n-1}}{n}\}_0^\infty\end{aligned} ::: ### 24. $證明\dfrac{f(x)}{(1-x)}為\ \{\begin{aligned}\sum_{j=0}^{n}a_j\end{aligned}\}_0^\infty\ 的生成函數，一般稱\dfrac{1}{1-x}為數列\{a_n\}_0^\infty的求和算子$ :::spoiler solution 直接計算得 $\begin{aligned}\dfrac{f(x)}{(1-x)}&=(a_0+a_1x+a_2x^2+...)(1+x+x^2+...)\\&=a_0+(a_0+a_1)x+(a_0+a_1+a_2)x^2+...\\&= \sum_{n=0}^{\infty}\left(\sum_{j=0}^{n}a_j\right)x^n\end{aligned}$ 所以$\dfrac{f(x)}{(1-x)}為\ \{\begin{aligned}\sum_{j=0}^{n}a_j\end{aligned}\}_0^\infty\ 的一般生成函數$ ::: <div style="display: grid; justify-content: center; align-content: center;"> | Column 1 | Column 2 | Column 3 | | -------- | -------- | -------- | | Text | Text | Text | ![](https://placekitten.com/200/300) </div> ![](https://placekitten.com/200/300)