Recursive Equations

We can calculate the first several terms 0, 1, 3, 7, 15, and we are tempted to guess the solution as \(a_n=2^n-1\). The previous formula can be easily established using mathematical induction but we will solve the problem using generating functions.

Let \(A(x)\) be the generating function of the sequence \(a_n\), i.e. let \(A(x)=\sum_n a_nx^n\). If we multiply both sides of the recurrent relation by \(x^n\) and add for all \(n\) we get \[\sum_n a_{n+1}x^n=\frac {A(x)-a_0}x= \frac {A(x)}x=2A(x)+\frac 1{1-x}= \sum_n (2a_n+1)x^n.\] From there we easily conclude \[A(x)=\frac x{(1-x)(1-2x)}.\] Now the problem is obtaining the general formula for the elements of the sequence. Here we will use the famous trick of decomposing \(A\) into two fractions each of which will have the corresponding generating function. More precisely \[\frac x{(1-x)(1-2x)}=x\left(\frac 2{1-2x} - \frac 1{1-x} \right)= (2x+2^2x^2+\cdots)-(x+x^2+\cdots).\] Now it is obvious that \(A(x)=\sum_{n=0}^{\infty} (2^n-1)x^n\) and the solution to the recurrent relation is indeed \(a_n=2^n-1\).

Let \(\{a_n\}_0^\infty \genfrac{}{}{0pt}{}{os}{\leftrightarrow} A\). Then \(\{a_{n+1}\}_0^\infty \genfrac{}{}{0pt}{}{os}{\leftrightarrow} \frac {A-1}x\). We also have that \(xD\frac 1{1-x} \genfrac{}{}{0pt}{}{os}{\leftrightarrow} \{n\cdot1\}\). Since \(xD\frac 1{1-x}=x\frac 1{(1-x)^2}=\frac x{(1-x)^2}\) the recurrent relation becomes \[\frac{A-1}x=2A+\frac x{(1-x)^2}.\] From here we deduce \[A=\frac {1-2x+2x^2}{(1-x)^2(1-2x)}.\] Now we consider that we have solved for the generating series. If we wanted to show that the sequence is equal to some other sequence it would be enough to show that the functions are equal. However we need to find the terms explicitely. Let us try to represent \(A\) again in the form \[\frac {1-2x+2x^2}{(1-x)^2(1-2x)}=\frac P{(1-x)^2}+\frac Q{1-x}+\frac R{1-2x}.\] After multiplying both sides with \((1-x)^2(1-2x)\) we get \[1-2x+2x^2=P(1-2x)+Q(1-x)(1-2x)+R(1-x)^2,\] or equivalently \[1-2x+2x^2=x^2(2Q+R)+x(-2P-3Q-2R)+(P+Q+R).\] This implies \(P=-1\), \(Q=0\), and \(R=2\). There was an easier way to get \(P\), \(Q\), and \(R\). If we multiply both sides by \((1-x)^2\) and set \(x=1\) we get \(P=-1\). Similarly if we multiply everything by \(1-2x\) and plug \(x=\frac 12\) we get \(R=2\). Now substituting \(P\) and \(R\) and setting \(x=0\) we get \(Q=0\).

Thus we have \[A=\frac {-1}{(1-x)^2}+\frac 2{1-2x}.\] Since \(\dfrac 2{1-2x} \genfrac{}{}{0pt}{}{os}{\leftrightarrow} \{2^{n+1}\}\) and \(\frac 1{(1-x)^2}=D\frac 1{1-x} \genfrac{}{}{0pt}{}{os}{\leftrightarrow} \{n+1\}\) we get \(a_n=2^{n+1}-n-1\).

Let \(F\) be the generating function of the series \(\{F_n\}\). If we multiply both sides by \(x^n\) and add them all, the left-hand side becomes \(\{F_{n+1}\} \genfrac{}{}{0pt}{}{os}{\leftrightarrow} \frac{F-x}x\), while the right-hand side becomes \(F+xF\). Therefore \[F=\frac x{1-x-x^2}.\] Now we want to expand this function into power series. First we want to represent the function as a sum of two fractions. Let \[-x^2-x+1=(1-\alpha x)(1-\beta x).\] Then \(\alpha=(1+\sqrt5)/2\), \(\beta=(1-\sqrt5)/2\), and \(\alpha-\beta=\sqrt 5\). We further have \[ \frac x{1-x-x^2}=\frac x{(1-x\alpha)(1-x\beta)}=\frac 1{\alpha - \beta} \left(\frac 1{1-x\alpha} - \frac 1{1-x\beta}\right)\] \[ =\frac 1{\sqrt5}\left\{\sum_{n=0}^{\infty} \alpha^nx^n-\sum_{n=0}^{\infty} \beta^nx^n\right\}. \] It is easy to obtain \[F_n=\frac 1{\sqrt5}(\alpha^n-\beta^n). \]

We know that the result is \(\binom{n}{k}\), but we want to obtain this using the generating functions. Assume that the required number is equal to \(c(n,k)\). Let \(A=\{a_1,\dots,a_n\}\) be an \(n\)-element set. There are two types of \(k\)-element subsets -- those which contain \(a_n\) and those that don’t. There are exactly \(c(n-1,k-1)\) subsets containing \(a_n\). Indeed they are all formed by taking \(k-1\)-element subsets of \(\{a_1,\dots, a_{n-1}\}\) and adding \(a_n\) to each of them. On the other hand there are exaclty \(c(n-1,k)\) subsets not containing \(a_n\). Hence \[c(n,k)=c(n-1,k)+c(n-1,k-1).\] We also have \(c(n,0)=1\). Now we will define the generating function of the sequence \(c(n,k)\) for a fixed \(n\). Assume that \[C_n(x)=\sum_k c(n,k)x^k.\] If we multiply the recurrent relation by \(x^k\) and add for all \(k\geq1\) we get \[C_n(x)-1= (C_{n-1}(x)-1)+xC_{n-1}(x), \;\;\mbox{for each } n\geq0\] and \(C_0(x)=1\). Now we have for \(n\geq1\): \[C_n(x)=(1+x)C_{n-1}(x).\] We finally have \(C_n(x)=(1+x)^n\). Hence, \(c(n,k)\) is the coefficient near \(x^k\) in the expansion of \((1+x)^n\), and that is exactly \(\binom nk\).

If \(A\) is the generating function of the corresponding sequence then: \[\frac {A-2-0\cdot x-(-2)x^2}{x^3}= 6\frac {A-2-0\cdot x}{x^2}-11\frac{A-2}x+6A,\] from where we easily get \[A=\frac {20x^2-12x+2}{1-6x+11x^2-6x^3}= \frac {20x^2-12x+2}{(1-x)(1-2x)(1-3x)}.\] We want to find the real coefficients \(B\), \(C\), and \(D\) such that \[\frac {20x^2-12x+2}{(1-x)(1-2x)(1-3x)}= \frac B{1-x}+\frac C{1-2x}+\frac D{1-3x}.\] We will multiply both sides by \((1-x)\) and set \(x=1\) to obtain \(B=\frac {20-12+2}{(-1)\cdot(-2)}=5\). Multiplying by \((1-2x)\) and setting \(x=1/2\) we further get \(C=\frac {5-6+2}{-\frac 14}=-4\). If we now substitute the found values for \(B\) and \(C\) and put \(x=0\) we get \(B+C+D=2\) from where we deduce \(D=1\). We finally have \[A=\frac 5{1-x} - \frac 4{1-2x} + \frac 1{1-3x}=\sum_{n=0}^{\infty} (5-4\cdot2^n+3^n)x^n\] implying \(a_n=5-2^{n+2}+3^n\).

Let \(A\) be the generating function of the sequence. The recurrent relation can be written in the form \[\frac {A-0-2x}{x^2}=-4\frac {A-0}x-8A\] implying \[A=\frac {2x}{1+4x+8x^2}.\] The roots \(r_1=-2+ 2i\) and \(r_2=-2- 2i\) of the equation \(x^2+4x+8\) are not real. However this should interfere too much with our intention for finding \(B\) and \(C\). Pretending that nothing weird is going on we get \[\frac {2x}{1+4x+8x^2}=\frac B{1-r_1x}+\frac C{1-r_2x}.\] Using the trick learned above we get \(B=\frac {-i}2\) and \(C=\frac i2\).

Did you read everything carefully? Why did we consider the roots of the polynomial \(x^2+4x+8\) when the denumerator of \(A\) is \(8x^2+4x+1\)?! Well if we had considered the roots of the real denumerator we would get the fractions of the form \(\frac B{r_1-x}\) which could give us a trouble if we wanted to use power series. However we can express the denominator as \(x^2(8+4\frac 1x+\frac 1{x^2})\) and consider this as a polynomial in \(\frac 1x\)! Then the denumerator becomes \(x^2\left(\frac 1x-r_1\right)\cdot\left(\frac 1x-r_2\right).\)

Now we can proceed with solving the problem. We get \[A=\frac {-i/2}{1-(-2+2i)x}+\frac {i/2}{1-(-2-2i)x}.\] From here we get \[A=\frac {-i}2 \sum_{n=0}^{\infty}(-2+2i)^nx^n+\frac i2\sum_{n=0}^{\infty}(-2-2i)^nx^n,\] implying \[a_n=\frac {-i}2(-2+2i)^n+\frac i2(-2-2i)^n.\] But the terms of the sequence are real, not complex numbers! We can now simplify the expression for \(a_n\). Since \[-2\pm2i=2\sqrt2 e^{\frac {\pm3\pi i}4},\] we get \[a_n=\frac i2 (2\sqrt2)^n\left((\cos \frac{3n\pi}4-i\sin\frac{3n\pi}4)-(\cos \frac{3n\pi}4+i\sin \frac{3n\pi}4)\right),\] hence \(a_n=(2\sqrt2)^n\sin \frac {3n\pi}4.\) Written in another way we get

\[a_n=\left\{\begin{array}{rl} 0, & n=8k\newline (2\sqrt2)^n, & n=8k+6\newline -(2\sqrt2)^n, & n=8k+2\newline \frac 1{\sqrt2} (2\sqrt2)^n, & n=8k+1 \mbox{ ili } n=8k+3\newline -\frac 1{\sqrt2} (2\sqrt2)^n, & n=8k+5 \mbox{ ili } n=8k+7 . \end{array} \right.\]

Let \(X(t)\) be the generating function of our sequence. Using the same methods as in the examples above we can see that the following holds: \[\frac X{t^2}-6\frac Xt+9X=\frac 1{1-2t}+\frac t{(1-t)^2}.\] Simplifying the expression we get \[X(t)=\frac {t^2-t^3-t^4}{(1-t)^2(1-2t)(1-3t)^2},\] hence \[X(t)=\frac 1{4(1-x)^2}+\frac 1{1-2x}-\frac 5{3(1-3x)}+\frac 5{12(1-3x)^2}.\] The sequence corresponding to the first summand is \(\dfrac {n+1}4\), while the sequences for the second, third, and fourth are \(2^n\), \(5\cdot3^{n-1}\), and \(\dfrac {5(n+1)3^{n+1}}{12}\) respectively. Now we have

\[x_n=\frac {2^{n+2}+n+1+5(n-3)3^{n-1}}4. \]

We see that the sequence is well define because each term is defined using the terms already defined. Let the generating function \(F\) be given by \[F(x)=\sum_{n\geq1}f_nx^{n-1}.\] Multiplying the first given relation by \(x^{2n-1}\), the second by \(x^{2n}\), and adding all of them for \(n\geq 1\) we get: \[f_1+\sum_{n\geq1}f_{2n}x^{2n-1}+ \sum_{n\geq1}f_{2n+1}x^{2n}= 1+\sum_{n\geq1}f_{n}x^{2n-1}+\sum_{n\geq1}f_{n}x^{2n}+ \sum_{n\geq1}f_{n+1}x^{2n}\] or equivalently \[\sum_{n\geq1}f_{n}x^{n-1}=1+\sum_{n\geq1}f_{n}x^{2n-1}+\sum_{n\geq1}f_{n}x^{2n}+\sum_{n\geq1} f_{n+1}x^{2n}.\] This exactly means that \(F(x)=x^2F(x^2)+xF(x^2)+F(x^2)\) i.e. \[F(x)=(1+x+x^2)F(x^2).\] Moreover we have \[F(x)=\prod_{i=0}^\infty \left(1+x^{2^i}+x^{2^{i+1}}\right).\] We can show that the sequence defined by the previous formula has an interesting property. For every positive integer \(n\) we perform the following procedure: Write \(n\) in a binary expansion, discard the last _quot_block_quot_ of zeroes (if it exists), and group the remaining digits in as few blocks as possible such that each block contains the digits of the same type. If for two numbers \(m\) and \(n\) the corresponding sets of blocks coincide the we have \(f_m=f_n\). For example the binary expansion of \(22\) is \(10110\) hence the set of corresponding blocks is \(\{1,0,11\}\), while the number \(13\) is represented as \(1101\) and has the very same set of blocks \(\{11,0,1\}\), so we should have \(f(22)=f(13)\). Easy verification gives us \(f(22)=f(13)=5\). \indent From the last expression we conclude that \(f_n\) is the number of representations of \(n\) as a sum of powers of two, such that no two powers of two are taken from the same set of a collection \(\{1,2\}\), \(\{2,4\}\), \(\{4,8\}\).