Recursive combinatorics with numbers and operators I have the following question that I have difficulty to grasp:
A string from 0,1,+,-,*,/
There are 2 rules:
1) string must start and end with a number.
2) string must not have two operators one after another.
The lecturer answer is f(n)=2f(n-1)+8f(n-2), while f(n) is the number of possible strings of length n, answering on said rules.
While 2f(n-1) is clear 8f(n-2) is not, as it creates possible duplications.
Any idea?
Thanks.
 A: A string of length $n$ can end either in a digit or in an operator. If it ends in a digit, it is the concatenation of any string of length $n-1$, of which there are $f(n-1)$, with any digit, of which there are $2$, which accounts for $2f(n-1)$. If it ends in an operator, it is the concatenation of any string of length $n-2$, of which there are $f(n-2)$, with any digit, of which there are $2$, and any operator, of which there are $4$, which accounts for $4\cdot2\cdot f(n-2)=8f(n-2)$.
A: OK, consider a valid sequence. It is either:


*

*Just a 0

*Just a 1

*A valid sequence, followed by 0 or 1

*A valid sequence, followed by an operator $+$, $-$, $*$, $/$, and one of 0 or 1


Pulling the different alternatives together:
$$
f(n + 2) = 2 f(n + 1) + 8 f(n) \quad f(0) = 1, f(1) = 2
$$
Can even solve explicitly: Define $F(z) = \sum_{n \ge 0} f(n) z^n$, using properties of ordinary generating functions:
$$
\frac{F(z) - f(0) - f(1) z}{z^2} = 2 \frac{F(z) - f(0)}{z} + 8 F(z)
$$
I.e.:
$$
F(z) = \frac{1}{1 - 2 z - z^2}
$$
By partial fractions this splits into two geometric series, unfortunately somewhat messy:
$$
F(z) = \frac{1}{2^{3/2} (1 + \sqrt{2})} \cdot \frac{1}{1 + z(1 + \sqrt{2})^{-1})}  - \frac{1}{2^{3/2} (1 - \sqrt{2})} \cdot \frac{1}{1 - z(1 + \sqrt{2})^{-1})}
$$
From here:
$$
f(n) = \frac{1}{2^{3/2} (1 + \sqrt{2})} (\sqrt{2} - 1)^{-n} - \frac{1}{2^{3/2} (1 - \sqrt{2})} (\sqrt{2} + 1)^{-n}
$$
(I hope I didn't mistype what Maxima gave)
