I'm having this recurrence that is giving me a lot of trouble.
$$F(2^0) = 1$$
$$F(2^k) = \frac 1 2 F(2^{k-1}) + 2^k$$
I will edit my post since this does not seems to work...
The initial recurrence is :
$$F(1) = n$$ $$F(n) = \frac 12 F(\lfloor\frac n 2\rfloor) + n$$
So I tried to resolve it for $$n = 2^k$$
So i have :
$$ 1/2^{k-i} * F(2^{k-i}) + \sum\limits_{j=k-i+1}^{k} 2^j $$
With k=i, at final I get 2n-1... Where did I messed up ?
You seem to be on the right track. Just keep going until you see a pattern.
$\begin{align} F(2^k) &= n + \frac 1 2 F(2^{k-1}) \\ &= n + \frac 1 2 (n + \frac 1 2 F(2^{k-2})) && = n + \frac n 2 + \frac 1 {2^2} F(2^{k - 2}) \\ &= n + \frac n 2 + \frac 1 {2^2} (n + \frac 1 2 F(2^{k - 3})) && = n + \frac n 2 + \frac n {2^2} + \frac n {2^3}F(2^{k - 3}) \\ & \dots \\ &= n + \frac n 2 + \frac n {2^2} + \frac n {2^3} + \frac n {2^4} + \dots + \frac n {2^j}F(2^{k - j}) \end{align} $
Eventually $k=j$ and so the last $F(2^{k - j}) = 1$. Got a little geometric sum there.