1

Solve the following recurrence relation $$f(1)=1, f(2)=2\\ f(x) = f\left(\left \lfloor \frac{x}{2} \right \rfloor\right) + f\left(\left\lfloor \frac{x}{3} \right\rfloor\right), \forall x \in \mathbb{N}, x \geq 3 $$

I tried the simple ways to solve a recurrence relation but got things messed up. Any Hint will be helpful.

Rezwan Arefin
  • 3,106
  • 1
  • 14
  • 39
  • 1
    https://oeis.org/A082479 and $$f(6k)=f(3k)+f(2k)$$ $$f(6k+1)=f(3k)+f(2k)$$ $$f(6k+2)=f(3k+1)+f(2k)$$ $$f(6k+3)=f(3k+1)+f(2k+1)$$ $$f(6k+4)=f(3k+2)+f(2k+1)$$ $$f(6k+5)=f(3k+2)+f(2k+1)$$ not much of a help though. – rtybase Mar 25 '17 at 17:32

1 Answers1

1

Is $x$ constrained in some particular set?

Note that:

$$ \begin{aligned} f(2) &= f\left(\left\lfloor \frac{2}{2} \right\rfloor\right) + f\left(\left\lfloor \frac{2}{3} \right\rfloor\right)\\ &=f(1) + f(0) \end{aligned} $$

Therefore, $f(0) = f(2) - f(1) = 1$. At the same time, for $x=1$,

$$ \begin{aligned} f(1) &= f\left(\left\lfloor \frac{1}{2} \right\rfloor\right) + f\left(\left\lfloor \frac{1}{3} \right\rfloor\right)\\ &=2f(0), \end{aligned} $$

therefore, $f(x) = \tfrac{1}{2}f(1) = \tfrac{1}{2}$, which is a contradition. Therefore, $f$ cannot be defined (at least) at $x=0$.

Pantelis Sopasakis
  • 5,155