High School Mathematics Extensions/Counting and Generating Functions/Solutions

[[../|Counting and Generating Functions]]

These solutions were not written by the author of the rest of the book. They are simply the answers I thought were correct while doing the exercises. I hope these answers are useful for someone and that people will correct my work if I made some mistakes.

Generating functions exercises

1.

(a)$S=1-z+z^2-z^3+z^4-z^5+...$

$zS=z-z^2+z^3-z^4+z^5-...$

$(1+z)S=1$

$S=\frac{1}{1+z}$

(b)$S=1+2z+4z^2+8z^3+16z^4+32z^5+...$

$2zS=2z+4z^2+8z^3+16z^4+32z^5+...$

$(1-2z)S=1$

$S=\frac{1}{1-2z}$

(c)$S=z+z^2+z^3+z^4+z^5+...$

$zS=z^2+z^3+z^4+z^5+...$

$(1-z)S=z$

$S=\frac{z}{1-z}$

(d)$S=3-4z+4z^2-4z^3+4z^4-4z^5+...$

$z(S+1)=4z-4z^2+4z^3-4z^4+4z^5-...$

$S+z(S+1)=3$

$S+zS+z=3$

$(1+z)S=3-z$

$S=\frac{3-z}{1+z}$

2.

(a)$S=\frac{1}{1+z}$

$S=\frac{1}{1--z}$

$S=1-x+x^2-x^3+x^4-x^5+...$

$f(n)=(-1{)}^n$

(b)$S=\frac{z^3}{1-z^2}$

$(1-z^2)S=z^3$

$S=z^3+z^5+z^7+z^9+...$

$f(n)=1;\text{for n}\ge 2\text{ and even}$

$f(n)=0;\text{for n is odd}$

2c only contains the exercise and not the answer for the moment

(c)$\frac{z^2-1}{1+3z^3}$

Linear Recurrence Relations exercises

This section only contains the incomplete answers because I couldn't figure out where to go from here.

1.

$\begin{array}{ccccc}{x}_n& =& 2x_{n-1}& -& 1;\text{for n}\ge 1\\ x_0& =& 1\end{array}$

Let G(z) be the generating function of the sequence described above.

$G(z)=x_0+x_{1}z+x_2{z}^2+...$

$(1-2z)G(z)=x_0+(x_1-2x_0)z+(x_2-2x_1)z^2+...$

$(1-2z)G(z)=1-z-z^2-z^3-z^4-...$

$(1-2z)G(z)=1-z(1+z+z^2+...)$

$(1-2z)G(z)=1-\frac{z}{1-z}$

$(1-2z)G(z)=\frac{1-2z}{1-z}$

$G(z)=\frac{1}{1-z}$

$x_n=1$

2.

$\begin{array}{ccccc}3x_n& =& -4x_{n-1}& +& x_{n-2};\text{for n}\ge 2\\ x_0& =& 1\\ x_1& =& 1\end{array}$

Let G(z) be the generating function of the sequence described above.

$G(z)=x_0+x_{1}z+x_2{z}^2+...$

$(3+4z-z^2)G(z)=3x_0+(3x_1+4x_0)z+(3x_2+4x_1-x_0)z^2+(3x_3+4x_2-x_1)z^3+...$

$(3+4z-z^2)G(z)=3x_0+(3x_1+4x_0)z$

$(3+4z-z^2)G(z)=3+7z$

$G(z)=\frac{3+7z}{-z^2+4z+3}$

3. Let G(z) be the generating function of the sequence described above.

$G(z)=x_0+x_{1}z+x_2{z}^2+...$

$(1-z-z^2)G(z)=x_0+(x_1-x_0)z+(x_2-x_1-x_0)z^2+(x_3-x_2-x_1)z^2+...$

$(1-z-z^2)G(z)=1$

$G(z)=\frac{1}{1-z-z^2}$

$G(z)=\frac{-1}{z^2+z-1}$

We want to factorize $f(z)=z^2+z-1$ into $(z-\alpha )(z-\beta )$ , by the converse of factor theorem, if (z - p) is a factor of f(z), f(p)=0.

Hence α and β are the roots of the quadratic equation $z^2+z-1=0$

Using the quadratic formula to find the roots:

$\alpha =\frac{\sqrt{5}-1}{2},\beta =-\frac{\sqrt{5}+1}{2}$

In fact, these two numbers are the famous golden ratio and to make things simple, we use the greek symbols for golden ratio from now on.

Note:$\frac{\sqrt{5}-1}{2}$ is denoted $\varphi$ and $\frac{\sqrt{5}+1}{2}$ is denoted $\mathrm{\Phi }$

$G(z)=\frac{-1}{(z-\varphi )(z+\mathrm{\Phi })}$

By the method of partial fraction:

$G(z)=\frac{1}{\sqrt{5}(z+\mathrm{\Phi })}-\frac{1}{\sqrt{5}(z-\varphi )}$

$G(z)=\frac{1}{\mathrm{\Phi }\sqrt{5}(\frac{z}{\mathrm{\Phi }}+1)}-\frac{1}{\varphi \sqrt{5}(\frac{z}{\varphi }-1)}$

$G(z)=\frac{1}{\mathrm{\Phi }\sqrt{5}(1--\varphi z)}+\frac{1}{\varphi \sqrt{5}(1-\mathrm{\Phi }z)}$

$x_n=\frac{\varphi }{\sqrt{5}}\times (-\varphi {)}^n+\frac{\mathrm{\Phi }}{\sqrt{5}}\times {\mathrm{\Phi }}^n$

$x_n=\frac{{\mathrm{\Phi }}^{n+1}-(-\varphi {)}^{n+1}}{\sqrt{5}}$

Further Counting exercises

1. We know that

$T(z)=\frac{1}{(1-z{)}^2}=\sum _{i=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{i+1}{i})z^i=\sum _{i=0}^{\mathrm{\infty }}(i+1)z^i$

therefore

$T(z)=\frac{1}{(1+z{)}^2}=\sum _{i=0}^{\mathrm{\infty }}(i+1)(-1{)}^i{z}^i$

Thus

$T_k=(-1{)}^k(k+1)$

2. $a+b+c=m$

$T(z)=\frac{1}{(1-z{)}^3}=\sum _{i=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{i+2}{i})z^i$

Thus

$T_k=(\genfrac{}{}{0ex}{}{i+2}{i})$

*Differentiate from first principle* exercises

1.

$f^{\prime }(z)=\underset{h\to 0}{\lim }\frac{1}{(1-(z+h){)}^2}-\frac{1}{(1-z{)}^2}=$

$\underset{h\to 0}{\lim }\frac{1}{h}\frac{(1-z{)}^2-(1-(z+h){)}^2}{(1-z-h{)}^2(1-z{)}^2}=$

$\underset{h\to 0}{\lim }\frac{1}{h}\frac{z^2-2z+1-(z+h{)}^2+2(z+h)-1}{(1-z-h{)}^2(1-z{)}^2}=$

$\underset{h\to 0}{\lim }\frac{1}{h}\frac{z^2-2z+1-z^2-h^2-2zh+2z+2h-1}{(1-z-h{)}^2(1-z{)}^2}=$

$\underset{h\to 0}{\lim }\frac{1}{h}\frac{-h^2-2zh+2h}{(1-z-h{)}^2(1-z{)}^2}=$

$\underset{h\to 0}{\lim }\frac{-h-2z+2}{(1-z-h{)}^2(1-z{)}^2}=$

$\frac{-2z+2}{(1-z{)}^4}=$

$\frac{-2}{(1-z{)}^3}$