Solve a non-linear recurrence analytically

Question

I have a recurrence: $$f_n = 1/n*f^2_{n/2} + n $$ where $T(1)=2$ and $n$ is a power of 2 and I want to solve it analytically not asymptotically. I cannot find bibliography for such type where a $T(n)$ term is in exponent greater than $1$ .

I tried substitution but I think get's complicated.

Answer 1

The recurrence can be written as

$$ \frac{f_n}{n} = \frac 14\left(\frac{f_{\frac n2}}{\frac n2}\right)^2+1 $$

calling now $g_n = \frac{f_n}{n}$ the recurrence can be recast as

$$ g_n = \frac 14 g_{\frac n2}^2+1 $$

making $n = 2^k$ we have

$$ g_{2^k}=\frac 14 g_{2^{k-1}}^2+1 $$

and can be recast as

$$ s_k = \frac 14 s_{k-1}^2+1 $$

at this point, as $f(1) = s_0 = 2$ we have

$s_1 = s_2=\cdots = s_k = 2$

and going backwards we have

$$ g_{2^k} = 2 = \frac{f_{2^k}}{2^k}=\frac {f_n}{n} = 2 $$

and finally

$$ f_n = 2n $$

Answer 2

Answer: $f_n=2n$.

Proof:

1. $f_1=2$;
2. $\frac{1}{n}f_{n/2}^2+n=\frac{1}{n}\left(2\frac{n}{2}\right)^2+n=n+n=2n=f_n$. $\quad\square$