MHB Solve Recurrence Equation w/2 Base Cases Same Result

  • Thread starter Thread starter ATroelstein
  • Start date Start date
  • Tags Tags
    Base Recurrence
AI Thread Summary
The recurrence equation presented is T(n) = 0 for n = 0, n = 1, and T(n) = T((n-1)/2) + 2 for n > 1. Unrolling the equation leads to T(n) = T((n-2^k+1)/2^k) + 2k, with k solved as log(n+1) - 1. The closed form derived is T(n) = 2(log(n+1) - 1), but proving its correctness encounters issues with the base case T(0) = 0. It is concluded that the boundary conditions for n = 0 and n = 1 are inconsistent with the recurrence relation for n ≥ 2, suggesting the need for a piecewise solution.
ATroelstein
Messages
15
Reaction score
0
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.
 
Physics news on Phys.org
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.
$$
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top