Solving recurrence relations [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 8 years ago.

Improve this question

I honestly don't even know if i am doing this right. The questions asks to solve:

C0 = 1

CN = CN/2 + N

when N is a power of 2.

Here is what I have so far but it is a complete guess

CN = CN/2 + N

CN/2 = CN/4 + N/2

CN = CN/4 + N/2 + N

stuck here

Answer 1

Observe that for each term, you are adding something to the next term. Thus, you'll get a sum. For example, for 1024, you'll get:

1024 + 512 + 256 + 128 + 64 + 32 + 16 + ...

As dividing a nonzero number by two will never yield zero, the base case, C0, is never reached, and you'll end up with an infinite series. Luckily, it is geometric. The initial term is N and each time we multiply by 1/2, so the the sum will be N/(1-1/2) = N/(1/2) = 2N.