Solution to recurrence relation: $f(x) = f(x-2)+f(x/2)$ for even $x$, $f(x)=f(x-1)$ for odd $x$.

Question

I need to find a solution for, or at least a way to compute efficiently, the following recurrence equation:

$$f(x) = \begin{cases} f(x-2)+f(x/2), & \text{if $x$ is even} \\ f(x-1), & \text{if $x$ is odd.} \end{cases}$$

Also, $f(0)=f(1)=1$.

I looked back at my notes from college years, none of the ones we studied look similar to this form, none of them has anything like $x/2$ in indexes.

Any help is greatly appreciated.

Answer 1

Note that we can write this as

$$f(n) = \begin{cases} f(n-1)+f(n/2), & \text{if $n$ is even} \\ f(n-1), & \text{if $n$ is odd.} \end{cases}$$

Now, consider the function $F(x)=\sum_{n\ge0}f(n)x^n$, and split its terms according to the parity of $n$:

$$F(x)=\sum_{n\ge0}f(n)x^n=\sum_{n \text{ even}}f(n)x^n+\sum_{n \text{ odd}}f(n)x^n$$

$$=\sum_{n \text{ even}}[f(n-1)+f(n/2)]x^n+\sum_{n \text{ odd}}f(n-1)x^n$$

$$=\sum_{n\ge0}f(n-1)x^n+\sum_{n\ge0}f(n)x^{2n}=xF(x)+F(x^2)$$

$$\implies (1-x)F(x)=F(x^2) \implies F(x)=\frac{F(x^{2^{n+1}})}{(1-x)(1-x^2)(1-x^4)...(1-x^{2^n})} $$

Using that $F(0)=1$, and with a little care about convergence, we can see that

$$F(x)=\prod_{n\ge 0}\frac{1}{1-x^{2^n}}$$

and this matches up nicely with @Giovanni Resta's claim that this is the number of partitions of $n$ into powers of $2$.

Answer 2

Generating the first terms and looking up them in the OEIS it turns out this sequence is A018819, i.e., Binary partition function: number of partitions of n into powers of 2.

In the OEIS you will find several biblio refs about this sequence and some formulas and connections with other combinatorial problems.

However, all the explicit formulas reported seems to express $a(n)$ in terms of previous values.