5
$\begingroup$

Consider the following recurrence relation: $$T(n) = 0 \text{ when } n \leq 0\\ T(n) = 1+\sum_{p=0}^{\infty}T\left(\left\lfloor\frac{n}{2^p}\right\rfloor - 1\right)$$ The first few integers generated by this relation are as follows: $$0, 1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70, 83, 101, 119, 142, 165, 195, 225, 262, 299$$ This was calculated using the following Python function:

def T(n):
    if n <= 0:
        return 0
    else:
        total = 1
        while n > 0:
            total += T(n - 1)
            n = n >> 1
        return total

I have the following questions:

  • Does this relation have a closed form (or how might one attack finding such a form)? The OEIS does not appear to know this sequence yet.
  • How does this function behave in the limit? It appears to be growing slightly faster than polynomial.
$\endgroup$
2
  • $\begingroup$ what's $x$? also, u start sum at $p=0$? $\endgroup$ Commented May 30, 2022 at 13:19
  • $\begingroup$ Oops, $x = n$, and I had a typo in the sum. Good eye! $\endgroup$
    – Lasse
    Commented May 30, 2022 at 13:23

1 Answer 1

10
$\begingroup$

$\newcommand{\fl}[1]{\lfloor #1\rfloor} \newcommand{\Fl}[1]{\Big\lfloor #1\Big\rfloor}$For natural $n\ge2$, we have \begin{equation*} T(n)=T(n-1)+T(\lfloor n/2\rfloor). \tag{1}\label{1} \end{equation*}

Then, \eqref{1} implies
\begin{equation*} \ln T(n)\sim c_*\ln^2 n \tag{2}\label{2} \end{equation*} as $n\to\infty$, for $c_*:=1/\ln4$.

Proofs of \eqref{1} and \eqref{2} will be given at the end of this answer.


The convergence in \eqref{2} seems to be very slow. Here is the graph $\Big\{\Big(n,\dfrac{\ln T(n)}{c\ln^2 n}\Big)\colon n\in\{2,\dots,10000\}\Big\}$

enter image description here


Proof of \eqref{1}: For any integer $n\ge1$, \begin{align} T(n)&=1+\sum_{p=0}^\infty T\Big(\Fl{\frac n{2^p}}-1\Big) \tag{3}\label{3} \\ &=1+T(n-1)+\sum_{p=1}^\infty T\Big(\Fl{\frac n{2^p}}-1\Big) \tag{4}\label{4} \\ &=1+T(n-1)+\sum_{j=0}^\infty T\Big(\Fl{\frac{n/2}{2^j}}-1\Big). \tag{5}\label{5} \end{align} So, if $n$ is even, then \eqref{3}, with $n/2$ in place of $n$, implies \begin{align} T(n)&=1+T(n-1)+T(n/2)-1, \notag \end{align} so that \eqref{1} holds if $n$ is even.

Suppose now that $n=2m+1\ge2$ is odd, so that $m\ge1$. Then for all integers $j\ge0$ \begin{equation*} \Fl{\frac{n/2}{2^j}} =\Fl{\frac{m+1/2}{2^j}}=\Fl{\frac m{2^j}}. \tag{6}\label{6} \end{equation*} (To prove the latter equality in \eqref{6}, suppose it is false. Then $k:=\fl{\frac m{2^j}}\le \frac{m+1/2}{2^j}-1$, whence $m<(k+1)2^j\le m+1/2$, which is a contradiction, since $(k+1)2^j$ and $m$ are integers.)

So, by \eqref{3}--\eqref{5}, \begin{align*} T(n)&=1+T(n-1)+\sum_{j=0}^\infty T\Big(\Fl{\frac m{2^j}}-1\Big) \\ &=1+T(n-1)+T(m)-1=T(n-1)+T(\lfloor n/2\rfloor), \end{align*} so that \eqref{1} holds as well if $n$ is odd.

This completes the proof of \eqref{1}. $\quad\Box$


To prove \eqref{2}, we need

Lemma 1: For real $c>0$ and natural $n$, let \begin{equation*} t_c(n):=e^{c\ln^2 n}. \end{equation*} Recall that $c_*=1/\ln4$. Then we have the following:

  • For each $c\in(0,c_*)$ there is a natural $n_c$ such that for all natural $n>n_c$ \begin{equation*} t_c(n)\le t_c(n-1)+t_c((n-1)/2) \\ \le t_c(n-1)+t_c(\fl{n/2}). \tag{7}\label{7} \end{equation*}

  • For each $c\in(c_*,\infty)$ there is a natural $n_c$ such that for all natural $n>n_c$ \begin{equation*} t_c(n)\ge t_c(n-1)+t_c(n/2)\ge t_c(n-1)+t_c(\fl{n/2}). \tag{8}\label{8} \end{equation*}

Proof of Lemma 1: The second inequality in \eqref{7} is trivial. Dividing both sides of the first inequality in \eqref{7} by $t_c(n-1)$, one can rewrite it as \begin{equation*} \exp\Big\{c\ln\frac n{n-1}\,\ln(n^2-n) \Big\}-1 \le\frac{e^{c\ln^2 2}}{(n-1)^{c\ln4}}. \end{equation*} The left-hand side of the latter inequality is $\sim\dfrac{2c}n\,\ln n$ and its right-hand side is $\sim\dfrac{e^{c\ln^2 2}}{n^{c/c_*}}$. So, the statement of Lemma 1 for $c\in(0,c_*)$ follows.

The statement of Lemma 1 for $c\in(c_*,\infty)$ is proved quire similarly.

This completes the proof of Lemma 1. $\quad\Box$

Let us now complete the proof of \eqref{2}. Take any $c\in(0,c_*)$ and let $n_c$ be a natural number as in Lemma 1. Since $T(n)>0$ for all $n\ge1$, we have \begin{equation*} T(n)\ge a_c t_c(n) \tag{9}\label{9} \end{equation*} for some real $a_c>0$ (depending only on $c$) and all natural $n\le n_c$. So, by \eqref{1}, \eqref{7} of Lemma 1, and induction on $n$, for all natural $n>n_c$ we have \begin{equation*} T(n)=T(n-1)+T(\fl{n/2})\ge at_c(n-1)+at_c(\fl{n/2}) \ge at_c(n). \end{equation*} Thus, \eqref{9} holds for each $c\in(0,c_*)$, some real $a_c>0$, and all natural $n$.

Similarly using \eqref{8} instead of \eqref{7}, we see that \begin{equation*} T(n)\le b_c t_c(n) \tag{10}\label{10} \end{equation*} for each $c\in(c_*,\infty)$, some real $b_c>0$ (depending only on $c$), and all natural $n$.

Finally, \eqref{2} follows from \eqref{9} for $c\in(0,c_*)$ and \eqref{10} for $c\in(c_*,\infty)$. $\quad\Box$

$\endgroup$
6
  • $\begingroup$ Interesting. In fact, it appears that $T(n)$ is equal to the recurrence $\{U(0) = 1/2; U(n) = U(n-1) + U(\lfloor n/2 \rfloor)\}$ for $n > 0$. Although I don't understand why yet. $\endgroup$
    – Lasse
    Commented May 30, 2022 at 18:41
  • $\begingroup$ @Lasse, at a guess the lemma you're missing is that if $y = \left\lfloor \tfrac xa \right\rfloor$ then $\left\lfloor \tfrac yb \right\rfloor = \left\lfloor \tfrac x{ab} \right\rfloor$. $\endgroup$ Commented May 30, 2022 at 18:58
  • $\begingroup$ @Lasse : I have now provided complete details. $\endgroup$ Commented May 30, 2022 at 21:39
  • $\begingroup$ Thanks for the careful analysis! Now that I know this simplified recurrence, it is easier to find closely related OEIS sequences: Sequence A000123 is equal to $\{U(0) = 1; U(n) = U(n-1) + U(\lfloor n/2 \rfloor)\}$. $\endgroup$
    – Lasse
    Commented May 31, 2022 at 11:52
  • 2
    $\begingroup$ This sequence comes up in the complexity analysis of a search algorithm. The algorithm is an attempt at Dijkstra's algorithm modified to use iterative deepening in such a way that it is efficient for search trees with both large branching factors and branching factors close to 1. In this algorithm, $T(n)$ measures the amount of nodes of the search tree that are visited on every iteration of the iterative deepening. Or in other words, $T(n)$ measures the computational budget available for search in a particular node, and how this budget is decreased when jumping to children. $\endgroup$
    – Lasse
    Commented Jun 1, 2022 at 7:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .