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.
 A: (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.
A: If the recurrence applies when $n=1$, so that $a=b$, it’s very easy to solve the recurrence without resorting to generating functions at all. Calculating by hand the first few terms of the sequence, we get the following results:
$$\begin{array}{rcc}
n:&0&1&2&3&4&5\\\hline
f_n:&a&a&2a&2a&3a&3a\\
&\\
n:&6&7&8&9&10&11\\\hline
f_n:&4a&4a&5a&5a&6a&6a\\
\end{array}$$
There’s a very evident pattern: it appears that $f_{2n}=f_{2n+1}=(n+1)a$, i.e., that $f_n=\left\lfloor\frac{n+2}2\right\rfloor a$. This is easily proved by induction on $n$:
$$\begin{align*}
f_{2(n+1)}&=f_{n+1}+f_n\\
&=\left(\left\lfloor\frac{n+3}2\right\rfloor+\left\lfloor\frac{n+2}2\right\rfloor\right)a\\
&=(n+2)a\,,
\end{align*}$$
where the final step can be done by considering the cases $n$ even and $n$ odd separately.
If $a\ne b$, however, so that the value of $f_1$ is an exception to the recurrence, it gets a good deal messier.
