Related to the [question about a(n)=a(n-1)+a(floor(n/2))](https://mathoverflow.net/questions/401272/bounds-for-an-an-1a-lfloor-n-2-rfloor)


Let $A$ be real constant $ 0 < A < 1$.


Define the sequence $a(n)$ by $a(1)=1, a(n)=a(n-1)+a(\lfloor n-n^A \rfloor)$


(if you prefer take $a'(n)=a'(n-1)+a'(n-\lfloor n^A \rfloor)$.



> 
> Q1 What are bounds for $a(n)$, especially good upper bound?
> 
> 
> 


If you prefer take $A=\frac12$.


We could't find the sequence in OEIS for $A=\frac12$.


We are interested if we can get $a(n)=\exp(o(n))$ (small oh on purpose).


**ADDED** As Iosif Pinelis points out, we must define $a(0)$, so
we define $a(0)=1$.



Bounds for the sequence $a(n)=a(n-1)+a(\lfloor n-n^A \rfloor)$
Let us show that
\begin{equation\*}
 a(n)\le\exp(n^{1-A+o(1)}) \tag{1}\label{1}
\end{equation\*}
(as $n\to\infty$).


Indeed, for each $q\in(1-A,1)$,
\begin{equation\*}
 (k-1)^q-k^q\sim-qk^{q-1},\quad (k-k^A)^q-k^q\sim-qk^{A+q-1}
\end{equation\*}
(as $k\to\infty)$, so that
\begin{equation\*}
 \frac{\exp((k-1)^q)+\exp((k-k^A)^q)}{\exp(k^q)} \\ 
 =1-(q+o(1))k^{q-1}+\exp(-(q+o(1))k^{A+q-1})
\end{equation\*}
and hence
\begin{equation\*}
 \exp((k-1)^q)+\exp((k-k^A)^q)\le\exp(k^q) \tag{2}\label{2}
\end{equation\*}
for some natural $K\_{A,q}$ (depending only on $A,q$) and for all natural $k\ge K\_{A,q}$.


Next, there exists a real $C\_{A,q}>0$ depending only on $A,q$ such that
\begin{equation\*}
 a(n)\le C\_{A,q}\exp(n^q) \tag{3}\label{3}
\end{equation\*}
for all $n\in\{0,\dots,K\_{A,q}-1\}$. Suppose that \eqref{3} holds for some natural $k\ge K\_{A,q}$ and all $n\in\{0,\dots,k-1\}$.
Then  

\begin{equation\*}
 a(k)=a(k-1)+a(\lfloor k-k^A\rfloor)\\ 
 \le C\_{A,q}\exp((k-1)^q)+C\_{A,q}\exp((k-k^A)^q)\big)
 \le C\_{A,q}\exp(k^q) 
\end{equation\*}
by \eqref{2}. So, \eqref{3} continues to hold for $n=k$. So, by induction on $n$, \eqref{3} holds for all natural $n$, if $q\in(1-A,1)$. This completes the proof of \eqref{1}.




---


If $a(0)\ge0$, then one can similarly obtain the corresponding lower bound on $a(n)$, to get  

\begin{equation\*}
 a(n)=\exp(n^{1-A+o(1)}) 
\end{equation\*}
(as $n\to\infty$).




---


Working a bit harder, we can get
\begin{equation\*}
 a(n)=\exp(n^{1-A}\ln^{1+o(1)}n) 
\end{equation\*}
(as $n\to\infty$). Such refinements can apparently go ad infinitum.


Anyhow, the requested bound $\exp o(n)$ on $a(n)$ has certainly been obtained.


