Exponential recurrence

Question

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.

Answer 1

(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.

Answer 2

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.