0
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ Why do you think that something here is wrong? $\endgroup$ – Vedran Šego Oct 10 '13 at 23:10
  • $\begingroup$ because this gives me 2n-1... $\endgroup$ – TUQWPORA32 Oct 11 '13 at 17:33
  • $\begingroup$ 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. $\endgroup$ – Vedran Šego Oct 11 '13 at 18:04
  • $\begingroup$ 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 + ... $\endgroup$ – TUQWPORA32 Oct 11 '13 at 18:07
  • $\begingroup$ 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$. $\endgroup$ – Vedran Šego Oct 11 '13 at 18:16
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – TUQWPORA32 Oct 11 '13 at 21:19
  • $\begingroup$ 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}$ $\endgroup$ – DanielV Oct 11 '13 at 21:27
  • $\begingroup$ ugh I am not sure I follow. What do you mean? $\endgroup$ – TUQWPORA32 Oct 11 '13 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.