find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ Find $O$ and $\Omega$ bounds as tight as possible for $T(n)=n+T(\frac n 2)+T(\frac n 4)+T(\frac n 8)+...+T(\frac n {2^k})$ 
while k is some constant and for any $n\leq3$, $\ T(n)=c$.
I didn't manage to find a tight upper bound. 
With rough evaluations i got $O(n^{logk})$ by $T(n) <  n+kT(\frac n 2)$
Also tried the following:
$T(n) = n+T(\frac{n}{2})+...+T(\frac{n}{2^{k}})$
$ = n+\sum_{i_{1}=1}^{k}\frac{n}{2^{i}}+\sum_{i_{1},i_{2}=1}^{k}T(\frac{n}{2^{i_{1}+i_{2}}})$
$ \vdots $
$ \leq n+\sum_{i_{1}=1}^{k}\frac{n}{2^{i}}+\sum_{i_{1},i_{2}=1}^{k}\frac{n}{2^{i_{1}+i_{2}}}+...+\sum_{i_{1},i_{2},...,i_{log(n)}=1}^{k}\frac{n}{2^{\sum_{j=1}^{log(n)}i_{j}}}$
$
 = n\left(1+\sum_{i_{1}=1}^{k}\frac{1}{2^{i}}+\sum_{i_{1},i_{2}=1}^{k}\frac{1}{2^{i_{1}+i_{2}}}+...+\sum_{i_{1},i_{2},...,i_{log(n)}=1}^{k}\frac{1}{2^{\left(\sum_{j=1}^{log(n)}i_{j}\right)}}\right)$
But i do not know how to continue from here.
Another attempt was changing variables: $2^m=n$ and  $U(m)=T(2^m)$ then $U(m)= 2^m+U(m-1) +...+U(m-k)$ but i did not manage to get any progress on that direction either.
Any help will be appreciated, thanks.
 A: Seems like if you guess that $T(n)\sim \alpha n$, then you have
$$
\alpha n \sim n +\alpha\left(\frac{n}{2}+\frac{n}{4}+\ldots+\frac{n}{2^k}\right)=n\left(1+\alpha\left(1-\frac{1}{2^k}\right)\right),
$$
which is consistent provided that $\alpha=2^k$.  For any fixed $k$, this will be the large-$n$ behavior (regardless of $c$, which only affects the small-$n$ behavior).
A: This can be done with the Akra-Bazzi method. Using Wikipedia's notation, the setup is
\begin{eqnarray*}
a_i \equiv 1 \\
b_i = 2^{-i} \\
h_i(x) \equiv 0 \\
g(x) = x \\
\end{eqnarray*}
The next step would be to solve 
$$f(p) \equiv \sum_{i=1}^k 2^{-ip} = 1$$
for $p$. But in this particular case we don't need to know what $p$ is. All we need to know is that $p \in (0,1)$, which you can check with the intermediate value theorem, noting that $f(0)=k>1$ and $f(1)=\sum_{i=1}^k 2^{-i} = 1-2^{-k} < 1$. So given such a $p$ the Akra-Bazzi method would say that
$$T(x) = \Theta \left ( x^p \left ( 1 + \int_1^x \frac{u}{u^{p+1}} du \right ) \right ) \\
= \Theta \left ( x^p \left ( 1 + \Theta \left ( x^{-p+1} \right ) \right ) \right ) \\
= \Theta(x)$$
A: We can solve  another closely related recurrence that  admits an exact
solution and makes it possible to get precise bounds.  Suppose we have
$T(0)=0$ and for $n\ge 1$ (this gives $T(1)=1$)
$$T(n) = n + \sum_{q=1}^p T(\lfloor n/2^q \rfloor).$$
Furthermore let the base two representation of $n$ be
$$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$
Then we  can unroll the  recurrence to obtain the  following exact
formula for $n\ge 1$
$$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor}
[z^j] \frac{1}{1-\sum_{q=1}^p z^q}
\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}.$$
This follows more or less by inspection.
Now to get an upper bound consider a string of one digits which yields
$$T(n) \le \sum_{j=0}^{\lfloor \log_2 n \rfloor}
[z^j] \frac{1}{1-\sum_{q=1}^p z^q}
\sum_{k=j}^{\lfloor \log_2 n \rfloor}  2^{k-j}
\\= \sum_{j=0}^{\lfloor \log_2 n \rfloor}
(2^{\lfloor \log_2 n \rfloor+1-j}-1)
[z^j] \frac{1}{1-\sum_{q=1}^p z^q}
\\= 2^{\lfloor \log_2 n \rfloor+1}
\sum_{j=0}^{\lfloor \log_2 n \rfloor}
\left(\frac{1}{2} \right)^j[z^j] \frac{1}{1-\sum_{q=1}^p z^q}
- \sum_{j=0}^{\lfloor \log_2 n \rfloor}
[z^j] \frac{1}{1-\sum_{q=1}^p z^q}.$$
Note that this bound is attained and cannot be improved. 
Since $(1/2)^j \le 1$ it is upper bounded by
$$(2^{\lfloor \log_2 n \rfloor+1} - 1)
\sum_{j=0}^{\lfloor \log_2 n \rfloor}
\left(\frac{1}{2} \right)^j[z^j] \frac{1}{1-\sum_{q=1}^p z^q}
\\ \le (2^{\lfloor \log_2 n \rfloor+1} - 1)
\sum_{j=0}^\infty
\left(\frac{1}{2} \right)^j[z^j] \frac{1}{1-\sum_{q=1}^p z^q}
\\= (2^{\lfloor \log_2 n \rfloor+1} - 1)
\frac{1}{1-\sum_{q=1}^p (1/2)^q}
\\= 2^p (2^{\lfloor \log_2 n \rfloor+1} - 1).$$
The lower bound is for the case of a one digit followed by a string of
zeros and yields
$$T(n) \ge \sum_{j=0}^{\lfloor \log_2 n \rfloor}
[z^j] \frac{1}{1-\sum_{q=1}^p z^q}
2^{\lfloor \log_2 n \rfloor-j}
\\= 2^{\lfloor \log_2 n \rfloor}
\sum_{j=0}^{\lfloor \log_2 n \rfloor}
\left(\frac{1}{2} \right)^j[z^j] \frac{1}{1-\sum_{q=1}^p z^q}.$$
At  this point  unfortunately we  cannot avoid  studying the  roots of
$$f(z) = 1-\sum_{q=1}^p z^q.$$ We need the root $\rho$ that is closest
to the origin  and more precisely, we have to show  that $\rho > 1/2.$
Since $f(0) = 1$ and $f(1) = - (p-1)$ we have at least one root $\rho$
in $(0, 1)$  and by the sign  and the continuity of $f'(z)$  it is the
only one. We must have  $\rho > 1/2$ since otherwise $\sum_{q=1}^p z^q
< 1$  because $p$  is finite. Furthermore  there are no  complex roots
with modulus $\rho$ because by  the triangle inequality there would be
cancellation and we would again have $|\sum_{q=1}^p z^q| < 1.$ This last
argument also applies to the  negative real negative root that appears
when $p$ is even.
The conclusion is that $\rho$ is the dominant singularity and
$$[z^j] \frac{1}{1-\sum_{q=1}^p z^q}
\sim -\frac{1}{\rho} \mathrm{Res}(1/f(z); z=\rho) \times \rho^{-j}
\\= \frac{1}{\sum_{q=1}^p q\times \rho^{q-1}} \times \rho^{-(j+1)}
= \frac{1}{\sum_{q=1}^p q\times \rho^q} \times \rho^{-j}.$$
Here we have used the fact that
$$\frac{1}{z-\rho} = - \frac{1}{\rho} \frac{1}{1-z/\rho}.$$
We have shown that
$$\sum_{j=0}^{\lfloor \log_2 n \rfloor}
\left(\frac{1}{2} \right)^j[z^j] \frac{1}{1-\sum_{q=1}^p z^q}
\sim \frac{1}{\sum_{q=1}^p q\times \rho^q}
\sum_{j=0}^{\lfloor \log_2 n \rfloor}
\left(\frac{1}{2\rho} \right)^j.$$
Now use the fact  that $\rho > 1/2$ to get $1  > 1/2/\rho$ to obtain
(geometric series)
that this sum  is bounded above by a constant that  does not depend on
$n.$

We are now ready to conclude. We have established that


*

* $T(n)$ is upper bounded by 
$2^p (2^{\lfloor \log_2 n \rfloor+1} - 1)$ 

* $T(n)$ is lower bounded by a multiple of  
$2^{\lfloor \log_2 n \rfloor}$  times a coefficient from
an interval that does not depend on $n.$



Joining the dominant terms of the upper and the lower bound we obtain
the asymptotics
$$\color{#006}{2^{\lfloor \log_2 n \rfloor}
\in \Theta\left(2^{\log_2 n}\right) 
= \Theta\left(n\right)}.$$
These are both in agreement with what the Master theorem would produce.
Remarks. This MSE link I and this MSE link II present closely related arguments. The calculation of the upper bound uses an annihilated coefficient extractor which is also used at this MSE link III.
A: This is a special case of
a previous problem I proposed and
partially solved:
If $T(n) = un + \sum_i T(\lfloor r_i n \rfloor) $, show that $T(n) = \Theta(n)$
My solution there does show that
$T(n) = \Theta(n)$
and conjectures that
$\dfrac{T(n)}{n}
\to 2^k$.
