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 hypothesis-making. Finding the exponent of best fit to a polynomial-ish 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 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

  • $\begingroup$ actually for $a=1$ $x_n=n(n-1)$, 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}=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.

  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.