For any $n\in\mathbb{Z}^+$, define a sequence $\{n_i\}$: $$ \begin{cases} n_0=n\\ n_{i+1}=\lceil n_i/2 \rceil + 1 \end{cases} $$ and $\{k_i\}$ are the terms to be added: $$ k_i = \lfloor n_i/2 \rfloor $$ $d$ is the length of the summation, $d \le \log_2{n}$.
I have worked out the following result: $$ \sum_{i=0}^{d-1} k_i \le (1-{1 \over 2^d})n+c_1d+c_2 $$ here $c_1,c_2$ are constants, and $c_1 \le 1.5$ .
But what I really want is to prove $c_1 \le 1$, and I believe it's true (by numeric tests).
Could anyone help me?
My Work $$ n_{i+1} \le {n_i +1 \over 2} + 1 = {n_i + 3 \over 2} \\ n_1 \le {n_0 + 3 \over 2} = {n \over 2} + {3 \over 2} \\ n_2 \le {n_1 + 3 \over 2} \le {n \over 4} + {3 \over 2} + {3 \over 4}\\ \vdots\\ n_i \le {n \over 2^i} + {3 \over 2} + {3 \over 4} + {3 \over 8} + \cdots + {3 \over 2^i}\\ n_i \le {n \over 2^i} + 3\\ k_i \le {n_i \over 2} \le {n \over 2^{i+1}} + 1.5\\ \sum_{i=0}^{d-1} k_i \le (1-{1 \over 2^d})n+1.5d $$
Background
I am trying to analyse the time complexity of Schönhage–Strassen algorithm, using recursion tree method.
Assume input size $N = 2^n$:
if $c_1 \le 1.5$, then $T(N)=O(N\log^{1.5}{N})$;
if $c_1 \le 1$ proved, then $T(N)=O(N\log{N}\log\log{N})$ proved.
By induction we can easily show that $n_i\ge \frac {n-1}{2^i}+1$. Also for each $i$ we have $k_i=n_i-n_{i+1}+1$. Thus
$$\sum_{i=0}^{d-1} k_i=\sum_{i=0}^{d-1} n_i-n_{i+1}+1=n+d-n_d\le (n-1)(1-2^{-d})+d.$$