Growth of sequence generated by recurrence relation 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.

 A: $\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\}$


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$
