Solving the recurrence: $h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1 $

Question

I want to solve the following recurrence:

\begin{equation} h(1) = 0\\ h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1 \end{equation}

What are some basic "methods" I can use to guess a closed form of this recurrence? I see that I am dividing by $d$ and this would mean that I am doing repeated division which would imply some sort of $\log_d$ term. Is this correct?

What is the closed form of this recurrence?

Answer 1

If it's
$$\begin{equation} h(0) = 0\\ h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1 \end{equation}$$ then $$h(i)=\left\lfloor \log_{d}{\frac{d-1}{d-2}i}\right\rfloor+1$$

Solution (I believe that it contains mistake I couldn't find because it gives different result):
Will use this later $$a\leq\left\lfloor\frac{i+1}{d} \right\rfloor < b \Longleftrightarrow ad-1\leq i < bd-1$$
Also such definition will be useful $$a_n=\min \left\{ i \vert f(i)=n\right\}$$

Then (without proof here) $$f(i)=n \Longleftrightarrow a_n \leq i<a_{n+1}$$

Because $f(i)=n+1$ iff $f\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)=n$
$$f(i)=n+1 \Longleftrightarrow a_n \leq \left\lfloor\frac{i+1}{d}\right\rfloor<a_{n+1}\\ f(i)=n+1 \Longleftrightarrow da_n-1 \leq i < da_{n+1}-1$$ So $$a_{n+1}=da_n-1, \ a_1=1, a_2=d-1$$ gives $$a_n=d^{n-1}-d^{n-2}-...-d-1=2d^{n-1}-\frac{d^n-1}{d-1}=\frac{(d-2)d^{n-1}+1}{d-1}$$

Next step is to get $n$ from inequalities $\frac{(d-2)d^{n-1}+1}{d-1}\leq i < \frac{(d-2)d^{n}+1}{d-1}$:
$$\frac{(d-2)d^{n-1}+1}{d-1}\leq i < \frac{(d-2)d^n+1}{d-1}\\ (d-2)d^{n-1}+1\leq (d-1)i < (d-2)d^n+1 \\ (d-2)d^{n-1}\leq (d-1)i-1 < (d-2)d^n \\ d^n\leq d\frac{(d-1)i-1}{d-2} < d^{n+1} \\ n=\left\lfloor \log_{d}{\frac{(d-1)i-1}{d-2}}\right\rfloor+1 $$ And $h(i)$ is equal to this value of $n$.