### Exercise

#### 3.20

Solve the recurrence $a_{n}=3 a_{n-1}-3 a_{n-2}+a_{n-3} \text { for } n>2$ with $a_0=a_1=0$ and $a_2=1$.

#### 3.28

Find an expression for $\left[z^{n}\right] \frac{1}{\sqrt{1-z}} \ln \frac{1}{1-z}$.

Hint. Expand $(1-z)^{-\alpha}$ and differentiate with respect to $\alpha$.

### Problem

#### 1

Which of these sequences is represented by the OGF $\frac 3 {1-z}$?

• 0, 0, 1/2, 0, 1/4, 0, 1/6, …

• 1, 3, 9, 27, 81, 243, …

• 3, 3, 3, 3, 3, …

• 1, 1 + 1/2, 1 + 1/2 + 1/3, …

• 0, 0, 1, 3, 6, 10, …

#### 2

Suppose that $a_{n}=9 a_{n-1}-20 a_{n-2}$ for $n>1$ with $a_{0}=0$ and $a_{1}=1 .$ What is the value of
$\lim _{n \rightarrow \infty} a_{n} / a_{n-1} ?$

#### 3

What is the value of $\sum_{0 \leq k \leq n}\left(\begin{array}{c}{2 k} \ {k}\end{array}\right)\left(\begin{array}{c}{2 n-2 k} \ {n-k}\end{array}\right) ?$