-
Using Rule 5, prove that [Wilf 38, example 6] $$F_0+F_1+\dots+F_n=F_{n+2}-1 \qquad \hbox{for
$n\ge 0$ }.$$solution
- Compare gfs of both sides, left is
$f/(1-x)$ , where$f = x/(1-x-x^2)$ , i.e. Fibonacci.
- Compare gfs of both sides, left is
-
Solve $$g_n=g_{n-1}+g_{n-2} \qquad\hbox{for
$n\ge 2$ }, \qquad g_0 = 0, \quad g_{10} = 10.$$solution
$g_n = {g_{10}\over F_{10}}F_n$ - try also the ``boundary method'' from the lecture, computer necessary
-
Solve [R16] $$a_n = \sum_{k=0}^{n-1}a_k \qquad\hbox{for
$n > 0$ }; \qquad a_0 = 1.$$solution
-
$a_n = 2^{n-1}$ for$n \ge 1$
-
-
Solve [Knuth 349/(7.41)] $$f_n=2f_{n-1}+f_{n-2}+f_{n-3}+\dots+f_1+1 \qquad\hbox{for
$n\ge 1$ }, \qquad f_0 = 0.$$solution
$F(x) = x/(1-3x+x^2)$ $f_n=F_{2n}$
-
Solve [K7.7] $$g_n = g_{n-1} + 2g_{n-2}+\dots +ng_0 \qquad\hbox{for
$n > 0$ }, \qquad g_0 = 1.$$solution
$G(x)=1+{x\over 1-3x+x^2}$ $g_n=F_{2n} + [n=0]$
-
Solve $$g_n = \sum_{k=1}^{n-1} {g_k + g_{n-k} + k\over 2} \qquad\hbox{for
$n\ge 2$ }, \qquad g_1 = 1.$$solution
TODO
-
Solve $$g_n=g_{n-1}+2g_{n-2}+(-1)^n \qquad\hbox{for
$n\ge 2$ }, \qquad g_0 = g_1 = 1.$$solution
$G(x) = {1+x+x^2\over (1-2x)(1+x)^2}$ $g_n = {7\over 9}2^n + {1\over 9}(3n+2)(-1)^n$
-
Solve [R24] $$a_{n+2}=3a_{n+1}-2a_n+n+1 \qquad\hbox{for
$n\ge 0$ }, \qquad a_0 = a_1 = 1.$$solution
$A(z) = {2\over 1-2z}-{1\over (1-z)^3}$ $a_n = 2^{n+1}-{n+2\choose 2}$
-
Prove that
$$\ln {1\over 1-x} = \sum_{n\ge 1} {1\over n} x^n.$$ solution
- consider
$\int {1\over 1-x}$
- consider