Solve Recurrence Equation w/2 Base Cases Same Result

[ATroelstein]

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.

 

[I like Serena]

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.
$$