MHB Recurrence relation - initial condition

[evinda]

Hello! (Smile)

I want to find the exact solution of the recurrence relation: $T(n)=2T(\sqrt{n})+1$.$$m=\lg n \Rightarrow 2^m=n \\ \ \ \ \ \ \ \ \ 2^{\frac{m}{2}}=\sqrt{n}$$

So we have: $T(2^m)=2T(2^{\frac{m}{2}})+1$

We set $T(2^m)=S(m)$, so we get: $S(m)=2S \left( \frac{m}{2}\right)+1$

$$S(m)=2S \left( \frac{m}{2}\right)+1=2^2S\left( \frac{m}{2^2} \right)+2+1= \dots= 2^i S \left( \frac{m}{2^i}\right)+ \sum_{j=0}^{i-1} 2^j$$If we would have an initial condition, let $S(1)=c$ then we would say that the recursion ends when $\frac{m}{2^i}=1$.

So that the recurrence relation is well-defined, it has to hold the following:

$$ n>\sqrt{n} \Rightarrow n^2>n \Rightarrow n^2-n>0 \Rightarrow n(n-1)>0 \Rightarrow n>1 \wedge n>0 \Rightarrow n \geq 2 \Rightarrow 2^m \geq 2 \Rightarrow m \geq 1$$So does this mean that we have to set $T(2)=S(1)=c$ ? (Thinking)

 

[jacobi1]

Your initial condition would probably have to be in terms of T(n), not S(n). You can find T(0)= -1 and T(1) = -1 from the equation, though.
If you use the method from my post in http://mathhelpboards.com/discrete-mathematics-set-theory-logic-15/solve-f-n-2f-sqrt-n-n-14405.html, you can find the solution of your recurrence to be
$$ T(n) = \left ( T(2) +1 \right ) \log_{2} n - 1, n = 2^{2^k}.$$
I'm not sure exactly how to solve this for T(2), though. If you take $ T(2) = 2 T( \sqrt 2 ) +1 $ and iterate, you have
$$ T(2) = 2^c T( \sqrt[c] 2 ) +2^{c} - 1 $$ for all $ c \geq 1 $.
Taking the limit, you get
$$ T(2) = \lim_{c \to \infty} \left ( 2^c - 2^c -1 \right ) = -1, $$
which implies that
$$ T(n) = ( -1 +1 ) \log_2 n -1 = -1 $$ for all n.
This seems to be really weird, until you take the limit as $ i \to \infty $ of the final recurrence relation in your post, which gives us the same answer.
Either I am horribly wrong, or this is the correct solution.