f(x) = ( f([x/2]) + f([x/3]) ) / 2

[Max]

There is a problem attracted certain attention in russian math forums recently.

Consider a function f(x) from the set of non-negative integers N to
the set of real numbers R such that
for x>=2, f(x) = ( f([x/2]) + f([x/3]) ) / 2 (here [.] denotes the
"floor" function).
It is asked if f(x) has a limit as x tends to infinity.

This problem is quite challenging and it took some time for people to
come up with a complete solution. It was solved using two different
approaches, namely, with Laplace transform and with an explicit
formula for f(x). For the first approach, see:
http://www.mathlinks.ro/Forum/viewtopic.php?p=499130 and
http://www.mathlinks.ro/Forum/viewtopic.php?t=28832
and for the second approach, see (these are in russian):
http://community.livejournal.com/ru_math/355678.html and
http://lib.mexmat.ru/forum/viewtopic.php?t=2399 (this thread talks
about generalizations).

The explicit formula for f(x) leads to several interesting sequences
missing in OEIS (and I am going to submit them). Below I summarize
some facts.

Suppose that f(0)=a and f(1)=b. Then it can be shown that
f(x) = a + g(x)*(b-a)
where g(x) can be explicitly defined as
g(x) = \sum_{k=0}^{[log3(x)]} binomial( k + [log2(x/3^k)], k ) / 2^( k
+ [log2(x/3^k)] )

Therefore, lim f(x) = a + L*(b-a) where L = lim g(x) and it was proved
that L=log6(4)=0.7737056...

It is easy to see that for any non-negative integer x, f(x) is a
linear combination of its first two values a=f(0) and b=f(1), i.e.,
f(x) = ( u(x)*a + v(x)*b ) / 2^[log2(x)]
where u(x) and v(x) are integers. In particular, for x=0..20 we have
u = [1, 0, 1, 0, 1, 1, 1, 1, 3, 1, 1, 1, 2, 2, 2, 2, 5, 5, 3, 3, 3]
v = [0, 1, 1, 2, 3, 3, 3, 3, 5, 7, 7, 7, 6, 6, 6, 6, 11, 11, 13, 13, 13]
It is easy to see that for x>=1, u(x) + v(x) = 2^[log2(x)].

It is worth to consider a special case of x=2^n. In this case we have
f(2^n) = (u(2^n)*a + v(2^n)*b) / 2^n
with u(2^n) + v(2^n) = 2^n. In particular, for n=0..16 we have
u(2^n): [0, 1, 1, 3, 5, 7, 13, 27, 53, 103, 205, 427, 917, 1959, 4077,
8251, 16341]
v(2^n): [1, 1, 3, 5, 11, 25, 51, 101, 203, 409, 819, 1621, 3179, 6233,
12307, 24517, 49195]

 From the explicit formula above it follows that
v(2^n) = \sum_{k=0}^{[n*log3(2)]} binomial( n + [k*c], k ) / 2^[k*c]
where c = 1-log2(3) = -0.5849625...
We can claim that lim v(x)/x = L and lim u(x)/x = 1-L as x tends to infinity.

This problem can be easily generalized (and produce more sequences).
For example, we can can consider a function defined by
f(x) = p_1*f([x/q_1]) + ... + p_k*f([x/q_k])
where p_i are positive rationals with p_1+...+p_k=1 and q_i are
positive integers whose logarithms are incommensurable. E.g.:
f(x)=(f([x/2])+f([x/3])+f([x/5]))/3 etc. etc.

Max