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.
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).