Closed form/upper bound for sequence $f(n+1)=f(n)-\sqrt{f(n)}, f(1)=n$ More precisely, given the sequence
$$f(1)=n;\quad f(n+1)=f(n)-\sqrt{f(n)}$$
I want to know if
$$\sum_{i=1}^{\log n} f(i)$$ has an upper-bound tighter than $O(n\log n)$, such as $O(n)$.
 A: Your definition uses $n$ for two different purposes. Mathematically, it would be better to write the definition as the following:


*

*$f(1)=n$ for some constant $n$.

*$f(m+1)=f(m)-\sqrt{f(m)}$ for all integers $m \geq 1$. 


Further, this definition might not always make sense, in particular, if $f(m)<1$, we have $f(m+1)<0$ and then $f(m+2)$ is not a real number. But, since we really only need to know $f(m)$ for $m \leq \log n$ to compute this sum, this is not a problem for sufficiently large $n$. 

Now, note that $f(m+1)<f(m)$ for all integers $m$, so $f$ is decreasing. In particular $f(m) < f(1) = n$ for all integers $m$. This means $$f(m+1)=f(m)-\sqrt{f(m)} > f(m)-\sqrt{n}$$
Now, one can prove by induction that $f(m) \geq n - (m-1)\sqrt{n}$. Therefore $f(\log(n)) \geq n - (\log(n)-1)\sqrt{n} \geq n - \log(n)\sqrt{n}$.
Therefore $\displaystyle \sum_{i=1}^{\log n} f(i) \geq \log (n) f(\log n) \geq n\log (n)- \log^2(n)\sqrt{n}$
Hence this sum is $\Omega(n\log n)$, i.e. there is no better bound than $O(n \log n)$. 
