3

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.

Em.
  • 15,981
mustafa
  • 33
  • Somewhat reminds me of this kind of recursion: http://math.stackexchange.com/questions/1053112/finding-matrix-for-given-recurrence – DanielV Feb 13 '16 at 09:49
  • If you're generating these terms in sequence then a simple memoized recursive function is reasonably efficient. FWIW, I can generate the first 250,000 terms in Python on a 2GHz machine in under 1.5 seconds. – PM 2Ring Feb 13 '16 at 10:46
  • You still have your college notes? – Saikat Feb 13 '16 at 11:02

2 Answers2

3

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

πr8
  • 10,800
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.

Giovanni Resta
  • 2,368