Asymptotic growth of recurrence relation $x_n=\min\limits_{n_1+n_2=n}(a(x_{n_1}+x_{n_2})+2n_1n_2)$ Suppose $a>0$ . Define
$$x_n=\min_{n_1+n_2=n}(a(x_{n_1}+x_{n_2})+2n_1n_2) \text{ with } x_1=0.$$ 
Can we find $r>0$ such that there exists two positive constant $c_1,c_2$ such that 
$$c_1<\frac{x_n}{n^r}<c_2$$ for sufficiently large $n$? If such $r$ exists, what is the value of $r$?
Thanks for your help.
 A: Some back-of-the-frontal-lobe calculations:
One gets $x_2=2$ and $x_3=2a+4$, given the limited number of sums.  For $x_4$, we have a choice of
$4a+8$ or $2a^2 +4a +6$, and for $x_5$ either $2a^2 +6a +12$ or $2a^3 +4a^2 +6a + 8$ or $4a^2 +8a +8$.
If $a \lt 1/2n$  then $x_i \lt 2i$ for $i$ up to $n$ and perhaps further.  If $a=0$, then $x_n =2(n-1)$, so if there is an $r$, it must be $r \geq 1$.  If $a \leq 1$, it should not be hard to show $x_n=O(n^2)$.  I imagine, but have not proved, that for $a>1$ $x_n$ is $O(a^{n/2})$.
Gerhard "Ask Me About System Design" Paseman, 2013.10.03
A: Based on numerical experiments I found that for $0<a<1$ the minimum is always at $n_{1}=1$ and $n_{2}=n-1$. This conjecture can be proven by induction in $n$ for an $a=1-\epsilon$ where $\epsilon>0$ and small. (I guess, if it is proven for $a$ near 1, i.e. to $O(\epsilon)$, it is true for all smaller $a$, because all coefficients of the resulting polynomial in $a$ are positive.) The solution then can be given in closed form:
$$
x_{n}=2\frac{n - 1 - n a + a^n}{(1-a)^{2}}.
$$
(It is a polynomial since the numerator has a double zero at $a=1$.) Thus $r=1$ for $0<a<1$ is correct.
Same as Pietro in his comment I found for $a>1$ (again by experiments using Mathematica) that
$$
x_{2^{m}}=2^{m} \frac{2^{m}-a^{m}}{2-a}
$$
which means (for $n=2^m$)
$$
x_{n}=\frac{n}{a-2}\left(a^{\ln n/\ln 2}-n\right)
$$
The latter is $O(n^{2})$ for $1<a<2$. For $a>2$ it has the more complicated asymptotics, $O(n a^{\ln n/\ln 2})$ (Edit: or, what is the same, $O(n^{1+\ln a/ \ln 2})$).
I could not prove formally the implicit assumption, that for $a>1$ the minimum in the recursion formula is at $n_{1}=n_{2}=n/2$ for $n$ even; and, for $n$ odd, $n_{1}=(n-1)/2$ and $n_{2}=(n+2)/2$. But I am pretty sure that I am right based on the results Mathematica gave me.
