c1.md

Exercises: generating functions (1)

Find explicit formulas for the following sequences:

1. $a_{n+1} = 3a_n+2$ for $n\ge 0$, $a_0=0$

   solution

   • $3x/(1-x)(1-3x)$
   • $3^n-1$

2. $a_{n+1} = \alpha a_n + \beta$ for $n\ge 0$, $a_0=0$

   solution

   • $\beta x/(1-x)(1-\alpha x)$
   • ${\alpha^n-1\over \alpha-1}\beta$

3. $a_{n+1} = a_n/3 +1$ for $n\ge 0$, $a_0=1$

   solution

   • ${3/2\over 1-x}-{1/2\over 1-x/3}$
   • ${3^{n+1}-1\over 2\cdot 3^n}$

4. $a_{n+2} = 2a_{n+1}-a_n$ for $n\ge 0$, $a_0=0$, $a_1=1$

   solution

   • $x/(1-x)^2$;
   • $n$

5. $a_{n+2} = 3a_{n+1}-2a_n+3$ for $n>0$, $a_0=1$, $a_1=2$

   solution

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

6. $a_n = 2a_{n-1}-a_{n-2}+(-1)^n$ for $n>1$, $a_0=a_1=1$

   solution

   • ${1/2\over (1-x)^2}-{1/4\over 1-x}+{1/4\over 1+x}$
   • ${2n+3+(-1)^n\over 4}$

7. $a_n = 2a_{n-1}-n\cdot(-1)^n$ for $n\ge 1$, $a_0=0$

   solution

   • ${x/9-2/9\over (1+x)^2}+{2/9\over 1-2x}$
   • ${2^{n+1}-(3n+2)(-1)^n\over 9}$

8. $a_n = 3a_{n-1} + {n\choose 2}$ for $n\ge 1$, $a_0=2$

   solution

   • ${1\over 8}(19\cdot 3^n-2n(n+2)-3)$

9. $a_n = 2a_{n-1}-a_{n-2}-2$ for $n > 1$, $a_0=a_{10}=0$

   solution

   • $n(a_1+1-n)$, so with $a_{10}$, $a_n=n(10-n)$

10. $a_n = 4(a_{n-1}-a_{n-2})+(-1)^n$ for $n \ge 2$, $a_0=1$, $a_1=4$

    solution

    • ${1+x+x^2\over (1+x)(1-2x)^2} = {1\over 9}{1\over 1+x} +\left({-5\over 18}\right) {1\over 1-2x} + \left({7\over 6}\right){1\over (1-2x)^2}$
    • ${1\over 9}(-1)^n-{5\over 18}\cdot 2^n+{7\over 6}(n+1)\cdot 2^n$

11. $a_n = -3a_{n-1}+a_{n-2}+3a_{n-3}$ for $n\ge 3$, $a_0=20$, $a_1=-36$, $a_2=60$

    solution

    • $5(-3)^n+18(-1)^n-3$

12. $a_n = -3a_{n-1}+a_{n-2}+3a_{n-3}+128n$ for $n\ge 3$, $a_0=0$, $a_1=0$, $a_2=0$

    solution

    • $8n^2+28n-29-11(-3)^n+40(-1)^n$