# Solving a recurrence with division

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 ?

• Why do you think that something here is wrong? – Vedran Šego Oct 10 '13 at 23:10
• because this gives me 2n-1... – TUQWPORA32 Oct 11 '13 at 17:33
• It was giving you exactly what DanielV wrote. I hope you understand his solution, but if you don't, feel free to write what seems to be the problem. I don't know if you can comment his answer; if not, comment here. – Vedran Šego Oct 11 '13 at 18:04
• His/my solution gives me $$1/2^{k-i} * F(2^{k-i}) + \sum\limits_{j= k-i+1}^{k} 2^j$$ which can't be right since the answer to that is : 2n-1. Answer should be (my intuition) something like 1/n + ... – TUQWPORA32 Oct 11 '13 at 18:07
• Before you edited, your question had this: $\frac 1 {2^3} F(2^{k-3}) + \frac n {2^2} + \frac n {2^1} + n$. This is what Daniel wrote. So, take his solution and use this formula for $a=n$ and $r=1/2$. – Vedran Šego Oct 11 '13 at 18:16

\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.
• How would you write the sum of $$\frac{2^{k-3}}{2^3} + \frac{2^{k-2}}{2^2} + \frac{2^{k-1}}{2^1} + 2^k$$ for J values ? – TUQWPORA32 Oct 11 '13 at 21:19
• For $j$ values I would write it as $$\sum_{p = 0}^{j - 1} \frac {2^{k - p}} {2^p}$$ but if you are doing that then I think you are on the wrong track. The numerate should be a constant $n$, not $2^{k - p}$ – DanielV Oct 11 '13 at 21:27