Homework 5
-
Let \(F_n\) be the number of subsets of \([n] = \{1, \ldots, n\}\) that contain no two consecutive elements for integer \(n\). Find the recurrence that is satisfied by these numbers (do not forget about the base case), and write this recurrence in the form of the algebraic identity the generating function \(F(s) = \sum_{n \geq 0} F_n s^n\) satisfies.
Solution
\(F_{0}=1,F_{1}=2,F_{2}=4,F_{3}=7,F_{4}=F_{3}+1+(4-2)+1=11,F_{5}=F_{4}+1+(5-2)+1+2 =18\)
Thus we conclude that \(F_{n}=F_{n-1}+F_{n-2}\) and \(F_{0}=1,F_{1}=2\)
\(F(s)=F_{0}+F_{1}s+F_{2}s^{2}+...\)
\(s\cdot F(s)=\,\,\,\,\,\,\,\,F_{0}s+F_{1}s^{2}+F_{2}s^{3}+...\)
\(s^{2}\cdot F(s)=\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,F_{0}s^{2}+F_{1}s^{3}+ F_{2}s^{4}+...\)
If we consider \(F(s)-s\cdot F(s)-s^{2}\cdot F(s)=F_{0}+(F_{1}-F_{0})s+(F_{2}-F_{1}-F_{0})s^{2}+( F_{3}-F_{2}-F_{1})s^{3}+...\)
\(=1+s+0+0+...\)
So \(F(s)-s\cdot F(s)-s^{2}F(s)=1+s\) \(\iff\) \((1-s-s^{2})F(s)=1+s\)\(\iff\)\(F(s)=\frac{1+s}{1-s-s^{2}}\)
-
A function \(f\) is defined for all \(n \geq 1\) by the relations
- \(f(1) = 1\)
- \(f(2n) = f(n)\) for all \(n \geq 1\)
- \(f(2n+1) = f(n) + f(n+1)\) for all \(n \geq 1\)
Let \(F(s) = \sum_{n \geq 1} f(n) s^{n-1}\). Show that \(F(s) = (1 + s + s^{2})F(s^{2})\)
Solution
\(F(s)=1+f\left(2\right)s^{1}+f\left(3\right)s^{2}+...+f\left(n\right)s^{n-1}+\ldots +f\left(2n\right)s^{2n-1}+\cdots\)
\(F(s^{2})=1+f\left(2\right)s^{2}+f\left(3\right)s^{4}+...+f\left(n\right)s^{2n-2} +\ldots+f\left(2n\right)s^{4n-2}+\cdots\)
\(s\cdot F(s^{2})=s+f\left(2\right)s^{3}+f\left(3\right)s^{5}+...+f\left(n\right)s ^{2n-1}+\ldots+f\left(2n\right)s^{4n-1}+\cdots\)
\(s^{2}\cdot F(s^{2})=s^{2}+f\left(2\right)s^{4}+f\left(3\right)s^{6}+...+f\left(n \right)s^{2n}+\ldots+f\left(2n\right)s^{4n}+\cdots\)
Then \(F(s^{2})+s\cdot F(s^{2})+s^{2}\cdot F(s^{2})=1+s+\left(1+f\left(2\right)\right)s ^{2}+f\left(2\right)s^{3}+\left(f\left(2\right)+f\left(3\right)\right)s^{4}+f\left (3\right)s^{5}+\ldots\)
Then use property 2 and 3, we get \(F(s^{2})+s\cdot F(s^{2})+s^{2}\cdot F(s^{2})=1+s+f\left(3\right)s^{2}+f\left(4\right )s^{3}+f\left(5\right)s^{4}+f\left(6\right)s^{5}+\ldots=F\left(s\right)\)
Thus \((1+s+s^{2})F(s^{2})=F\left(s\right)\)
Check that \(\prod_{j \geq 0}^{\infty}\left(1 + s^{2^j}+ s^{2^{j+1}}\right)\) (whatever this infinite product means) solves this equation.
Solution
\(\prod_{j\geq0}^{\infty}\left(1+s^{2^{j}}+s^{2^{j+1}}\right)=\left(1+s+s^{2}\right )\left(1+s^{2}+s^{4}\right)\left(1+s^{4}+s^{8}\right)\ldots=\frac{F\left(s\right)}{F\left(s^{2}\right)} \frac{F\left(s^{2}\right)}{F\left(s^{4}\right)}\frac{F\left(s^{4}\right)}{F\left(s^{8}\right)} \ldots=\frac{F\left(s\right)}{F\left(s^{2^{j}}\right)}\) where \(j\to\infty\)
-
Similarly to the problem we have seen in the tutorial, find the number of subsets of \(\{1, \ldots, 2000\}\) such that the sum of their elements is divisible by 4.
Solution
We can see here the subsets such that sum of whose elements is divisible by 4 corresponds to the power of the \(s\)
Thus it means we just need to solve the sum of coefficients corresponding to \(s^{4},s^{8},...\),
We call the coefficients corresponding to the \(s\) is \(a_0,a_1,a_2,...\)
Consider the polynomial \(f(s)=\prod_{i=1}^{2000}\left(1+s^{i}\right)=\left\lbrack\left(1+s\right)\left(1+ s^{2}\right)\left(1+s^{3}\right)\left(1+s^{4}\right)\right\rbrack\ldots\)
\(=\left(1+s+s^{2}+2s^{3}+2s^{4}\right)\ldots=1+s+s^{2}+2s^{3}+2s^{4}+\cdots\)
Consider the unit roots of \(x^4=1\), the root is \(1,s,s^2,s^3\) and \((x-1)(x-s)(x-s^{2})(x-s^{3})=x^4-1\) (Consider \(x=-1,(1+1)(1+s)(1+s^{2})(1+s^{3})=0\))
Then \(f(1)=1+1+1+2\cdot1+2\cdot1+\cdots\)
\(f(s)=1+s+s^{2}+2s^{3}+2s^{4}+\cdots\)
\(f(s^2)=1+s^{2}+s^{4}+2s^{6}+2s^{8}+\cdots\)
\(f(s^3)=1+s^3+s^{6}+2s^{9}+2s^{12}+\cdots\)
Then \(f(1)+f(s)+f(s^{2})+f(s^{3})=4\cdot1+0+0+0+2\cdot4+...=4(a_{0}+a_{1}+a_{2}+a_{3}+ a_{4}+\cdots)\)
Thus the number we needed is \(\frac{1}{4}(f(1)+f(s)+f(s^{2})+f(s^{3}))\)
Clearly, \(f(1)=2^{2000}\), then \(f(s)=\left\lbrack\left(1+s\right)\left(1+s^{2}\right)\left(1+s^{3}\right)\left(1 +s^{4}\right)\right\rbrack\ldots\)
Since we know above \((1+1)(1+s)(1+s^{2})(1+s^{3})=0\), then \(f(s)=0\)
Similarly, \(f(s^2)=f(s^3)=0\), thus the number is \(\frac{2^{2000}}{4}=2^{1998}\)