10 Recursions and generating functions 10 Recursions and generating functions 10.2 Two-variable examples

10.1 One-variable examples

Exercise(A) 10.1.

Suppose that $a_{n+1}=2a_{n}+1,n\geq 1$ and $a_{0}=0$ . Show that

x^{-1}f(x)=2f(x)+91-x)^{-1}

and hence deduce that $a_{n}=2^{n}-1,n\geq 0.$

Exercise(A) 10.2.

Suppose that $a_{n+1}=2a_{n}+n,n\geq 1$ and $a_{0}=1$ . Prove that

x^{-1}(f(x)-1)=2f(x)+x(1-x)^{-2},

and deduce that $a_{n}=2^{n+1}-n-1.$

Exercise(A) 10.3.

Suppose that $a_{n+1}=a_{n+1}+a_{n-1},n\geq 1$ and $a_{0}=a_{1}=1$ . Prove that

x^{-1}(f(x)-x)=f(x)+xf(x),

and deduce that $a_{n}=\frac{1}{\sqrt{5}}(r_{+}^{n}-r_{-}^{n}),$ where $r_{+}=\frac{1+\sqrt{5}}{2}$ and $r_{-}=\frac{1-\sqrt{5}}{2}$ .

Example 10.4.

Let $d_{n}$ be the number of $n$ -derangements i.e., permutations of $[n]$ with no fixed points. Let $\pi$ be an $(n+1)$ -derangement. Suppose $\pi(n+1)=i\in[n]$ . If $\pi(i)=n+1$ , then the rest of the permutation is a derangement of $[n]\setminus\{i\}$ . If $\pi(i)\neq n+1=\pi(j)$ then replacing $\pi(j)$ by $i$ gives a derangement of $[n]$ . Thus, given $i\in[n]$ and a $n$ -derangement or $n-1$ -derangement, we can construct a $(n+1)-$ derangement and vice-versa.

d_{n+1}=n(d_{n-1}+d_{n}).

Set $d_{0}=1$ , $d_{1}=0$ , $d_{2}=1$ . Let $f$ be the EGF. Multiply both sides by $\frac{x^{n}}{n!}$ . Then, we have that

	$\displaystyle\sum_{n=1}d_{n+1}\frac{x^{n}}{n!}$	$\displaystyle=\sum_{n=0}nd_{n}\frac{x^{n-1}}{(n-1)!}=f^{\prime}(x);$
	$\displaystyle\sum_{n=1}nd_{n}\frac{x^{n}}{n!}$	$\displaystyle=x\sum_{n=1}d_{n}\frac{x^{n-1}}{(n-1)!}=xf^{\prime}(x);$
	$\displaystyle\sum_{n=1}nd_{n-1}\frac{x^{n}}{n!}$	$\displaystyle=x\sum_{n=1}d_{n-1}\frac{x^{n-1}}{(n-1)!}=xf(x).$

Thus, we have that $(1-x)f^{\prime}(x)=xf(x).$ So we have that

f(x)=(1-x)^{-1}e^{-x}=(\sum_{n=0}x^{n})(\sum_{n=0}\frac{(-x)^{n}}{n!})=(\sum_{% n}x^{n}\sum_{k=0}^{n}\frac{(-1)^{k}}{k!},

and so $d_{n}=\sum_{k=0}^{n}\frac{(-1)^{k}}{k!}.$

Example 10.5.

Consider the number of self-avoiding walks (SAW) of length $n$ going only up (U), left (L) or right (R). In other words, left cannot be followed by right and vice-versa. Let $a_{n}$ be the number of such paths.

Suppose if $b_{n}$ is the number of paths starting with a U. Call these U-paths. Then $b_{n}=a_{n-1}$ . Further concatenating a U-path of length $n$ and $m$ gives a $U$ -path of length $m+n$ . Thus $b_{n}$ is super-multiplicative and so by Fekete’s lemma, $b_{n}^{1/n}\to b_{*}$ and $b_{n}\leq 3^{n-1}$ trivially. We now derive more better bounds carefully.

The number of paths ending with U is $a_{n-1}$ . Else paths end with LL, RR, UL, UR. Consider $n-1$ SAWs. If it ends with L or R, let the final move be the same i.e., L or R respectively. If U, final move is L. The number of UR $n$ -SAWs is the number of $(n-1)$ -SAWs ending with U i.e., $a_{n-2}$ . We have shown that

a_{n}=2a_{n-1}+a_{n-2},\,n\geq 2\,\,;\,\,a_{0}=1,a_{1}=3

Let $f$ be OGF. Then,

f(x)=1+3x+2x(f(x)-1)+x^{2}f(x).

f(x)=\frac{1+x}{1-2x-x^{2}}=\frac{\alpha/2}{1-\alpha x}+\frac{\beta/2}{1-\beta x},

where $\alpha=1+\sqrt{2},\beta=1-\sqrt{2}.$ Therefore,

a_{n}=\frac{1}{2}(\alpha^{n+1}+\beta^{n+1}),

and so $a_{n}^{1/n}\to 1+\sqrt{2}$ .