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.

3$\begingroup$ Can you tell us something about the context? $\endgroup$ – Johan Wästlund Oct 3 '13 at 12:32

1$\begingroup$ Did you tried to check it numerically? It will be much easier to prove such statement by induction than to come up with one. $\endgroup$ – Rami Oct 3 '13 at 16:17

2$\begingroup$ I think that you can prove by induction that for any positive $\epsilon$ there exist $C_1,C_2$ s.t. $C_1 n^{log_2 a\epsilon}<x_n<C_2 n^{max(log_2 a,2)+\epsilon}$, for sufficiently large $n$. $\endgroup$ – Rami Oct 3 '13 at 16:37

$\begingroup$ This is begging for some numerical experimentation (for several $a$) and educated hypothesismaking. Finding the exponent of best fit to a polynomialish growing sequence is an easy computational task. $\endgroup$ – Greg Martin Oct 3 '13 at 21:54

$\begingroup$ I assume that both $n_1$ and $n_2$ are supposed to be strictly less than $n$. Then $x_1$ is not defined. $\endgroup$ – Eckhard Oct 3 '13 at 23:13
Some backofthefrontallobe 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(n1)$, 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

$\begingroup$ actually for $a=1$ $x_n=n(n1)$, so it is true what you say for $a\le 1$. $\endgroup$ – Pietro Majer Oct 4 '13 at 9:26
Based on numerical experiments I found that for $0<a<1$ the minimum is always at $n_{1}=1$ and $n_{2}=n1$. 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}{(1a)^{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}}{2a} $$ which means (for $n=2^m$) $$ x_{n}=\frac{n}{a2}\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}=(n1)/2$ and $n_{2}=(n+2)/2$. But I am pretty sure that I am right based on the results Mathematica gave me.

$\begingroup$ Do you mean $O(n^2)$ for $1<a<2$ and $O(n^{1+\ln a/\ln 2})$ for $a>2$? $\endgroup$ – Eckhard Jun 24 '14 at 18:38

$\begingroup$ Yes, my mistake. I corrected it. Thanks for the comment. $\endgroup$ – Johannes Trost Jun 25 '14 at 7:40