find a function satisfying the recurrence

Question

find a function satisfying the recurrence

$$F (n) = 2F (\sqrt{n}) + 1$$

replace $n$ by $2^m$ Thus getting the answer as $$F(n)=\frac{1}{2}c \log(n) + \log(n) - 1$$

Is this correct

Answer 1

Looks good: \begin{align} 2 F(\sqrt{n}) + 1 &= 2\left( \left(\frac{c}{2} + 1 \right) \log(\sqrt{n}) - 1 \right) + 1 \\ &= 2\left( \left(\frac{c}{2} + 1 \right) \frac{1}{2} \log(n) - 1 \right) + 1 \\ &= \left(\frac{c}{2} + 1 \right) \log(n) - 1 \\ &= F(n) \end{align}

You could replace the constant factor $c/2 + 1$ by another constant $d$.

In case you asked about the derivation as well (the wording of your question is somewhat ambigious to me):

Setting $n = 2^m$ gives the equation $$ F(2^m) = 2 F(2^{m/2}) + 1 $$

setting $F(2^m) = G(m)$ gives $$ G(m) = 2 G(m/2) + 1 \iff G(2k) = 2 G(k) + 1 $$

That looks pretty linear. Trying $G(k) = a k + b$ gives $$ 2 a k + b = 2 a k + 2 b + 1 \iff b = - 1 $$

So $G(m) = a m - 1$ and $F(2^m) = a m - 1 \iff F(n) = a \log_2(n) - 1 = c \ln(n) - 1$ for some constant $c$.