- Thread starter
- #1

#### ATroelstein

##### New member

- Jun 30, 2012

- 15

http://www.mathhelpboards.com/f15/solving-specific-variable-when-solving-recurrence-equation-3804/

I have a recurrence equation of the form

$$

T(n) = 0, n = 0, n = 1\\ T(n) = T(\frac{(n-1)}{2}) + 2, n > 1

$$

By unrolling the equation, I get (thanks to I like Serena's help ):

$$

T(n) = T\left(\frac{n-2^k+1}{2^k}\right) + 2k

$$

Now if I solve for k when

$$

\frac{n-2^k+1}{2^k} = 0

$$

I get

$$

k = log(n+1) - 1

$$

Substituting this back in

$$

T(n) = T(1) + 2*(log(n+1) - 1)\\

T(n) = 2*(log(n+1) - 1)

$$

Now if I wanted to prove my closed form is correct, I have to use induction. I can prove the base case of T(n) = 0 when n = 1. The problem results when I want to also show that the other base case of T(n) = 0 when n = 0. I ran through the full inductive proof and was able to show my closed form is correct, except that lingering base case of 0. How would I go about solving the equation so that I also take into consideration that base case as well? Thanks.