0

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

ivt
  • 1,587
  • I'm assuming that the recurrence formula is valid only if $n$ is a perfect square. Is it correct? I suspect that $F(n)$ can take any value if $n$ is not a perfect square, and the values that $F$ takes for such $n$ determine $F$. – ajotatxe Feb 05 '15 at 22:53
  • I think that $F(n)$ can take any positive integer and $F(\lceil\sqrt n\rceil)$ or $F(\lfloor\sqrt n\rfloor)$ is implied. At least, the proof given this implication is fine for me. – ivt Feb 05 '15 at 23:00
  • 2
    There's no difference between $\frac12 C[1]$ and $C[1]$. $C[1]$ is an arbitrary constant. – Greg Martin Feb 05 '15 at 23:03
  • That's what I thought, I can even combine the two logarithms. Is it wrong to believe that Mathematica had any particular reason to insert 1/2? – ivt Feb 05 '15 at 23:05

0 Answers0