Exponential recurrence Let $f_0 = a, f_1 = b$.
Define $f_n = f_{n-1}$ for odd $n$ and
$$f_{n} = f_{n/2}+f_{n/2 - 1}$$
How do I solve this recurrence? Normally I would use generating functions but the fraction is screwing me up.

(I will assume that "$f_n=f_{n-1}$ for odd $n$" includes $n=1$, so that $f_1=f_0$; if that's not the case, a similar method will apply but it gets more annoying.)
Define $F(x) = \sum_{n=0}^\infty f(n)x^n$ and $F_2(x) = \sum_{n\text{ even}} f(n)x^n$. Since $f_{n+1}=f_n$ when $n$ is even, we have $F(x) = F_2(x) + xF_2(x) = (1+x)F_2(x)$. On the other hand, since $f_{2m} = f_m + f_{m-1}$ (presumably for $m\ge1$),
\begin{align*}
F_2(x) = \sum_{m=0}^\infty f_{2m} x^{2m} &= f_0 + \sum_{m=1}^\infty (f_m + f_{m-1}) x^{2m} \\
&= f_0 + \bigg( {-}f_0 + \sum_{m=0}^\infty f_m x^{2m} \bigg) + \bigg( x^2 \sum_{m=1}^\infty f_{m-1} x^{2(m-1)} \bigg) \\
&= (1+x^2) F(x^2).
\end{align*}
Therefore
$$
F(x) = (1+x)F_2(x) = (1+x)(1+x^2) F(x^2).
$$
Replacing $x$ by $x^2$ gives $F(x^2) = (1+x^2)F_2(x^2) = (1+x^2)(1+x^4) F(x^4)$,
which means that
$$
F(x) = (1+x)(1+x^2)(1+x^2)(1+x^4) F(x^4).
$$
Repeating this process gives, for any $k\ge1$,
$$
F(x) = \prod_{j=0}^{k-1} (1+x^{2^j}) \prod_{j=1}^{k} (1+x^{2^j}) F(x^{2^k}).
$$
Taking the limit as $k\to\infty$ gives
$$
F(x) = \prod_{j=0}^\infty (1+x^{2^j}) \prod_{j=1}^\infty (1+x^{2^j}) f_0 = \frac1{1-x} \frac1{1-x^2} f_0,
$$
which we can check does satisfy the given recurrences.
