I'm stuck with the following recurrence relation: $F(n) = 2F(\sqrt n) + 1, n \in \mathbb{N}$
I considered $n = 2^{2^{k}}$ and then expanded the recursion and here is what I get $F(n) = F(2^{2^{k}}) = 2^{k}F(2) + 2^{k} -1$
Assuming, that we are looking for some kind of general solution, let $F(2) = c$ Then $F(n) = clog(n) + log(n) -1$
I'm wondering why is Mathematica giving a[n] -> -1 + Log[n] + 1/2 C[1] Log[n], specifically, where does the $1/2$ part come from?
Also, in case my arguments are valid, how can I prove that the formula is correct for all $n$, and not just $n = 2^{2^{k}}$