# Proving the solution of a recurrence equation with two base cases that have the same result

#### ATroelstein

##### New member
This question is related to the question that I have asked here, although the equation is ever so slightly different:
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.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Hi ATroelstein!

When we fill in n=1 in your recurrence relation $T(n) = T(\frac{n-1}{2}) + 2$, we get:
$$T(1) = T(\frac{1-1}{2}) + 2 = T(0)+2=0+2 \ne 0$$
So your boundary conditions for $n=0$ and $n=1$ cannot both be consistent with the recurrence relation for $n \ge 2$.
In other words, there is no solution with just one simple formula.

The solution you would be looking for, is for instance:
$$T(n) = \left\{\begin{array}{ll} 0 \quad &\text{ if } n=0 \\ 2(\log_2(n+1) - 1) \quad &\text{ if } n \ge 1 \\ \end{array}\right.$$