High School Mathematics Extensions/Counting and Generating Functions/Solutions

High School Mathematics Extensions

---

Supplementary Chapters — Primes and Modular Arithmetic — Logic

Mathematical Proofs — Set Theory and Infinite Processes — Counting and Generating Functions — Discrete Probability

Matrices — Further Modular Arithmetic — Mathematical Programming — Markov Chains

Counting and Generating Functions

At the moment, the main focus is on authoring the main content of each chapter. Therefore this exercise solutions section may be out of date and appear disorganised.

If you have a question please leave a comment in the "discussion section" or contact the author or any of the major contributors.

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;{\mbox{for n}}\geq 2{\mbox{ and even}}$

$f(n)=0;{\mbox{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{matrix}x_{n}&=&2x_{n-1}&-&1;\ {\mbox{for n}}\geq 1\\x_{0}&=&1\end{matrix}}$

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{matrix}3x_{n}&=&-4x_{n-1}&+&x_{n-2};\ {\mbox{for n}}\geq 2\\x_{0}&=&1\\x_{1}&=&1\\\end{matrix}}$

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 $\phi$ and ${\frac {{\sqrt {5}}+1}{2}}$ is denoted $\Phi$

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

By the method of partial fraction:

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

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

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

$x_{n}={\frac {\phi }{\sqrt {5}}}\times (-\phi )^{n}+{\frac {\Phi }{\sqrt {5}}}\times \Phi ^{n}$

$x_{n}={\frac {\Phi ^{n+1}-(-\phi )^{n+1}}{\sqrt {5}}}$

Further Counting exercises

1. We know that

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

therefore

$T(z)={\frac {1}{(1+z)^{2}}}=\sum _{i=0}^{\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}^{\infty }{i+2 \choose i}z^{i}$

Thus

$T_{k}={i+2 \choose i}$

*Differentiate from first principle* exercises

1.

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

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

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

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

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

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

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

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