How to convert recursive function into explicit form

Question

I have the recursive expression:

$$f(n) = 1 + f\left(\left\lceil {\frac{2n - 1}{6}} \right\rceil\right)\text{ for }n>1$$

and

$$f(0) = 0$$ $$f(1) = 0$$

And I'm trying to turn it into its explicit / closed form

I have tried generating functions but have failed miserably, any help with this or even a step in the right direction would help

Answer 1

Formulation of the problem

First of all, notice the necessity of having $n>1$ rather than $n\ge1$. Indeed, letting $n=1$ in the recursion leads to $f(1)=f(1)+1$ which has no solution. The same reasoning must exclude the point $n=0$. Since in these points the $f(n)$ is not defined by the recursion, these values are given externally. We shall see in a moment how these two parameters appear in the solution.

Hence I propose the following, more precise, formulation of the problem: find a closed form for the solution of the recursion

$$f(n) = 1 + f\left(\left\lceil {\frac{2n - 1}{6}} \right\rceil\right)\text{ for }n\ne0 \text{ and } n\ne1 \tag{1a}$$

for real $n$ and

$$f(0), f(1) = \text{arbitrary parameters}\tag{1b}$$

Solution

By just writing down the recursion for positive integers $n$ we have

$$f(2)=f(3)=f(1)+1$$ $$f(4..9)=f(2)+1=f(1)+2$$ $$f(10..27)=f(1)+3$$ etc.

From the pattern observed here we can see that $f(n)$ in the indicated intervals is given by

$$f\left(1+3^{k-1}\text{ .. } 3^{k}\right)=k+f(1), k\ge1\tag{2}$$

But we need not restrict ourselves to integers. Doing the same for real $n\gt 1$, renaming $n$ to $x$, we find a set of expressions for $f$ the start of which goes like this

$$\begin{align}f(x)=f(1)+1,1<x\leq \frac{7}{2}\\ f(x)=f(2)+1,\frac{7}{2}<x\leq \frac{13}{2} \\f(x)=f(3)+1,\frac{13}{2}<x\leq \frac{19}{2} \\f(x)=f(4)+1,\frac{19}{2}<x\leq \frac{25}{2}\end{align}\tag{3}$$

in general, for $k=2, 3, 4, ...$

$$\begin{align} & f_k(x)=f(k)+1\\ &\frac{6(k-2)+7}{2}\lt x \le \frac{6(k-1)+7}{2} \end{align}\tag{4}$$

$f(k)$ can be traced back using $(2)$ to the form $m +f(1)$ so that finally we find the closed expressions

$$\begin{align} & f(x)=f(1)+1,1<x\leq \frac{7}{2} \\ & f_k(x)=f(1)+k, \frac{1}{2} +3^{k-1}\lt x\leq \frac{1}{2}+ 3^k, k=2,3,... \end{align}\tag{5} $$

But we not yet finished. What about extending the range of $x$ below $x=1$?

By pluggin in rational values of $x$ into the recursion we find

$$f(x)=f(0)+1,0<x<1\\f(x)=f(-1)+1=f(0)+2,-5.5<x<0\\f(x)=f(-2)+1=f(0)+2,-8.5<x\leq -5.5\\f(x)=f(-3)+1=(f(-1)+1)+1=f(0)+3,-11.5<x\leq -8.5$$

First of all notice that $x=1$ and $x=0$ have to be excluded. The function is not defined in these points.

But for the whole range $x\lt0$ the function is well defined and can be traced back to the free parameter $f(0)$.

I leave it as an exercise to the reader to find the formula similar to $(5)$ in the range $x \lt 0$.

Summarizing, the recursion can be solved explicitly for all real values of $x$, except $x=0$ and $x=1$.

The solution has the simple form $f(x) = m+a$ where $m$ is a positive integer related to the specific range of $x$ and $a = f(0)$ for $x<1, x\ne 0$ and $a=f(1)$ for $x\gt 1$.

Hence the solution has two free parameters $f(0)$ and $f(1)$. That is why in the original OP these two values were reasonably given (and have been set to $0$).

Plot of the solution

The Mathematica code for reducing $f(x)$ to either $f(0)$ or $f(1)$ by replacements is

m[z_] := Module[{y = z}, 
  While[And [FreeQ[y, f[0]], FreeQ[y, f[1]]], 
   y = y /. f[k_] -> 1 + f[Ceiling[(2 k - 1)/6]]]; y]

Example:

In[366]:= {m[f[-2]], m[f[-1]], m[f[0]], m[f[1]], m[f[2]]}

Out[366]= {1 + f[0], 1 + f[0], f[0], f[1], 1 + f[1]}

In[9]:= Table[{k, m[f[k]]}, {k, -2, 2, 0.7}]

Out[9]= {{-2., 1 + f[0]}, {-1.3, 1 + f[0]}, {-0.6, 1 + f[0]}, {0.1, 
  1 + f[0]}, {0.8, 1 + f[1]}, {1.5, 1 + f[1]}}