c3.md

Exercises: (mostly) skipping sequence elements

1. Assume that $A(x)$ is the ogf for $(a_n)$. Express the generating function for $\sum_{n\ge 0} a_{3n}x^n$ in terms of $A(x)$.

   solution

   • ${1\over 3}(A(x^{1/3}) + A(\omega x^{1/3})) + A(\omega^2 x^{1/3})$, where $\omega=e^{2\pi i/3}$

2. Compute $S_n=\sum_{n\ge 0} F_{3n}\cdot 10^{-n}$ (by plugging a suitable value into the generating function for $F_{3n}$).

   solution

   • The gf is ${2x\over 1-4x-x^2}$ and $S_n=20/59$.

3. Compute $\sum_k {n\choose 4k}$.

   solution

   • $2^{{n\over 2} - 2} \left(2^{n\over 2} + \cos\left({1\over 4}n \pi\right) + (-1)^n \cos\left({3\over 4}n \pi\right)\right)$

4. Compute $\sum_k {6m\choose 3k+1}$.

   solution

   • Compute it for general $n$ and then plug in $n=6m$
   • $(2^{6m}-1)/3$

5. Evaluate $S_n = \sum_{0\le k\le n} (-1)^k k^2$.

   solution

   • $f(x) = {-x\over (1+x)^3}$
   • $S_n={1\over 2}(-1)^n n(n+1)$

6. Find ogf for $H_n = 1 + 1/2 + 1/3 + \dots$.

   solution

   • ${-\ln(1-x) \over 1-x}$

7. Find the number of ways of cutting a convex $n$-gon with labelled vertices into triangles.

   solution

   • $C_{n-2}$ (shifted Catalan numbers)