<s>[INST] $T(n) = 2T\left(\lfloor n/2\rfloor +1\right) + T(n-1) + 1$, $T(3) = 1$ I am looking for asymptotic bound on $T$, where $T$ satisfies the following recurrence:
$$T(n) = 2T\left(\lfloor{\frac{n}{2}\rfloor} +1\right) + T(n-1) + 1\text{ , }T(3) = 1.$$
I plotted the graph for $T$, and it seems like $T$ grows somewhere between a polynomial and an exponential. I want to know whether $T$ has exponential growth or slower growth.
 [/INST] Your prediction is correct, $T(n)$ has growth rate between polynomial and exponential. Let $F(x)$ be defined by $$
F(x) = \sum_{n=0}^\infty \frac{c_n (x-3)^n}{n!}
$$
where $c_n$ is defined by $c_0=1$ and $c_n = 3 \cdot 2^{-\binom{n-1}2}$ for $n\ge 1$. This series converges (quite rapidly, I would add) for all $x\in \mathbb{C}$.
Claim: For all $n\ge 3$ $$
F(n) \ge T(n) \ge C + (2C+1)F(n+3)
$$
where $C = \frac{1-F(6)}{1+2F(6)} \approx -0.477$.
We observe that $F(x)$ clearly has great-than-polynomial growth rate. It is an entire function with order $0$, which means that for any $\alpha >0$, $$
\lim\limits_{x\rightarrow\infty} \frac{F(x)}{\exp(x^\alpha)} = 0
$$
See 1.
Proof of upper bound: We observe that $c_{n+1} = 2^{1-n}c_n$ for $n\ge 1$, which implies \begin{eqnarray}
F'(x-1) &=& 2F(x/2 + 1) + 1
\end{eqnarray}
because \begin{eqnarray}
2F(x/2 + 1) + 1&=&
1+\sum_{n=0}^{\infty}\frac{2c_n(\frac x2 -2)^n}{n!} 
\\&=& 1+\sum_{n=0}^\infty \frac{2^{1-n}c_n(x-4)^n}{n!}\\
&=&3 + \sum_{n=1}^\infty \frac{2^{1-n}c_n (x-4)^n}{n!}\\
&=&\sum_{n=0}^\infty\frac{c_{n+1}(x-4)^n}{n!} = F'(x-1).\end{eqnarray}
We claim that $T(n) \le F(n)$ for all $n\ge3$, which can be shown inductively. It is trivial for $n=3$. We observe \begin{eqnarray}
T(n) &=& 2T(\lfloor n/2 \rfloor + 1)+T(n-1)+1\le 2 F(\lfloor n/2\rfloor + 1) + F(n-1) + 1 \\&\le& 2F(n/2 + 1) + F(n-1) + 1 = F'(n-1) +F(n-1)\\
&=& \int_{n-1}^{n} F'(n-1) dx + F(n-1) \le \int_{n-1}^n F'(x)dx + F(n-1)\\
&=& F(n)
\end{eqnarray}
where we make use of the fact that $F(x)$ is convex for $x\ge 3$.
Proof of lower bound: For convenience, denote $G(x) = C + (2C+1)F(x+3)$. We observe \begin{eqnarray}
G'(x) &=& (2C+1)F'(x+3) = (2C+1)(2F(\frac {x+4}2 + 1) + 1)\\&=&2(2C+1)F(\frac x 2 + 3) + 2C+1=2G(x/2) + 1
\end{eqnarray} and \begin{eqnarray}
G(3) &=& C + (2C + 1)F(6) = \frac{1-F(6)}{1+2F(6)} + 2\frac{F(6)-F(6)^2}{1+2F(6)}+F(6)\\
&=&\frac{1 + F(6) - 2F(6)^2}{1+2F(6)}+F(6) = \frac{(1-F(6))(1+2F(6))}{1+2F(6)} + F(6) = 1
\end{eqnarray}
We use induction to show that $T(n) \ge G(n)$ for all $n\ge 3$, using the above as our base case, we proceed (again making use of convexity):\begin{eqnarray}
T(n)&=&2T(\lfloor n/2 \rfloor + 1) + T(n-1)+1 \ge 2G(\lfloor n/2 \rfloor + 1) + G(n-1) + 1\\
&\ge& 2G(n/2) + G(n-1)+1= G'(n) + G(n-1) \\&\ge& \int_{n-1}^{n}G'(x)dx + G(n-1) = G(n)
\end{eqnarray}
completing the proof.
Update - Numerical demonstration: After doing some numerical simulations, it looks like $$
\lim_{n\rightarrow\infty} \frac{T(n)}{F(n)} \approx 0.2656...
$$
Here's a plot of the first thousand terms of the ratio $T(n)/F(n)$, with the horizontal red line at $y=0.2656$:

I did the computation all the way out to $50000$. The ratio stays flat on that line. It also looks like $$
\log F(x) \sim (\log x)^\alpha$$
for some $\alpha \approx 1.81$.
</s>