Prove conjecture $a_{n+1}>a_{n}$ if $a_{n+1}=a+\frac{n}{a_{n}}$

Solution 1:

A picture says more than a thousand words. Successive iterands must be read from the bottom to the top, following e.g. one of the vertical green lines:

Thirteen functions $a_k(a)$ with $k = 1,2,\cdots ,13$ are displayed; lower iterands with darker lines.
The viewport is:

xmin = 0; xmax = 5; ymin = 0; ymax = 5; 

Let's make a few calculations, for the sake of understanding the graphics: $$ a_1(a) = a\\ a_2(a) = \frac{a^2+1}{a}\\ a_3(a) = \frac{a(a^2+3)}{a^2+1}\\ a_4(a) = \frac{a^4+6a^2+3}{a(a^2+3)}\\ a_5(a) = \frac{a(a^4+10a^2+15}{a^4+6a^2+3} $$ That's enough to see the folowing fact:

• With odd $k$ in $a_k(a)$ the function is zero for $a=0$ : $\;a_{odd}(0) = 0$
• With even $k$ in $a_k(a)$ the function is singular for $a=0$ : $\;a_{even}(0) = \infty$

It is also noticed that the numerator of $a_k(a)$ always becomes the denominator of $a_{k+1}(a)$.
It is seen that the curves [ $a_2(a)$ and $a_3(a)$ ] , [ $a_4(a)$ and $a_5(a)$ ] , [ $a_6(a)$ and $a_7(a)$ ] , in general
[ $a_{even}(a)$ and $a_{even+1/odd}(a)$ ] each have an intersection point. For [ $a_2(a)$ and $a_3(a)$ ] this point is easy to find: $$ a + \frac{1}{a} = a + \frac{2}{a + \frac{1}{a}} \quad \Longrightarrow \quad 2a = a + \frac{1}{a} \\ \Longrightarrow \quad (a,a_2(a))=(a,a_3(a))=(1,2) $$ But if we want to find some other intersection points, considerable difficulties cross our path; even the help of a computer algebra system (like MAPLE) seems to be futile, with exact solutions.
So let's take a look instead at the ingenious conjecture as proposed by the OP: $$ n > \frac{4}{a^3} \quad \Longrightarrow \quad a > \left(\frac{4}{n}\right)^{1/3} $$ These values $a$ together with their function values $a_k(a)$ are displayed as red dots in the picture.
It is clearly seen that the conjecture is quite good, especially for larger values of $n$.
It is an approximation, though, and a sufficient condition at best, not a necessary condition.
But in order to formulate a sufficient and necessary condition, the above mentioned intersection points must be found, which seems at this moment a too hard task to accomplish.

EDIT. In order to solve for the points of intersection, equate $a_{n+1}$ to $a_n$ , noticing that $a_n > 0$ : $$ a_n = a_{n+1} = a + \frac{n}{a_n} \quad \Longrightarrow \quad a_n^2-a\cdot a_n-n = 0 \quad \Longrightarrow \quad a_n = \frac{a}{2} + \sqrt{\left(\frac{a}{2}\right)^2+n} $$ So now we know the ordinates of the intersection points. But, unfortunately, that doesn't give us any information about the abscissas $a$. What we can do is draw the $\color{blue}{\mbox{graphs}}$ of the new functions, name them $b_n(a)$ :

We expect that $b_n(a) = a_n(a) = a_{n+1}(a)$ at the intersection points. However, there is a difference between the curves in dark Blue and light blue (Aqua). The former are for $b_n(a)$ with $n = $ even; they intersect $a_n(a)$ and $a_{n+1}(a)$ as expected. The latter are for $b_n(a)$ with $n = $ odd; they do not intersect $a_n(a)$ and $a_{n+1}(a)$. But all blue curves $b_n(a)$ are somehow interesting, because they are asymptotes to the curves $a_n(a)$. For large values of $a$ we have almost straight lines: $$ b_n(a) = \frac{a}{2}+\frac{a}{2}\sqrt{1+\frac{n}{(a/2)^2}} \approx a + \frac{n}{a} $$ Still another way to calculate the intersection points is to determine the minimum of the curves $a_n(a)$ for $n = $ even. Which is easy to prove, because $a_n(a)\ne a/2$ in : $$ a_n^2(a)-a\cdot a_n(a)-n = 0 \quad \Longrightarrow \quad a_n'(a)\left[2 a_n(a)-a\right]= 0 \quad \Longrightarrow \quad a_n'(a)=0 $$ The slope of the accompanying odd curve at such a minimum is always $1$ , according to: $$ a_{n+1}'(a) = \left(a-\frac{n}{a_n(a)}\right)' = 1-\frac{n\, a_n'(a)}{a_n^2(a)} = 1 $$ Let's do some work with help of MAPLE:

> a_1 := a; a_2 := a+1/a_1; a_3 := a+2/a_2; a_4 := a+3/a_3; a_5 := a+4/a_4;

> fsolve(a_4=a_5,a,0..infinity);

                             0.8713379136

> fsolve(a_4=a/2+sqrt((a/2)^2+4),a,0..infinity);

                             0.8713379136

> fsolve(diff(a_4,a)=0,a,0..infinity);

                             0.8713379136

> subs(a=%,a_4);

                             2.482570870

Though I find it not very enlightning, in this case an exact solution can be found as well: $$ a_{4,5} = \sqrt{\left(8+6\sqrt{2}\right)^{1/3}-\frac{2}{\left(8+6\sqrt{2}\right)^{1/3}}-1}; $$ Continuing in this way (with some higher precision) gives the following results, before MAPLE and my own Newton-Raphson iterations give up. $$ \begin{matrix} {\bf \mbox{IP abscisssa} \; a} & {\bf n} & {\bf < 4/a^3} \\ 1 & 2,3 & 4 \\ 0.871337913570159 & 4,5 & 6.04644570004055 \\ 0.792253607266638 & 6,7 & 8.04391208677473 \\ 0.736268951824715 & 8,9 & 10.0219107501819 \\ 0.693502616556087 & 10,11 & 11.9926643644897 \\ 0.659225892899425 & 12,13 & 13.9623081896349 \\ 0.630825547822963 & 14,15 & 15.9342699607407 \\ 0.606713039185383 & 16,17 & 17.9105946558336 \end{matrix} $$ Herewith the conjecture is proved , for $\;n=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17$ .

POST BOUNTY. Geromty's conjecture has been proved now (numerically) for $n$ up to $10,000$ . The only limitation seems to be that one has to halt at some place. Our last line of output has been: $$ \begin{matrix} {\bf \mbox{IP abscisssa} \; a} & {\bf n} & {\bf < 4/a^3} \\ 0.0564535548737650 & 9998,9999 & 22232.3877129834 \end{matrix} $$ It is thus noticed that geromty's formula gives over-estimates by more than a factor $2$ for such large values of $n$ , that is: if our calculations can be trusted. If one is truly interested in a lower bound for $n$ such that $\,a_{n+1} > a_n$ , then one could think about employing the little computer program below, instead of the conjecture. Here is the (Pascal) source code of the executable that does the job:

program maple;

function quotient(n : integer; a : double) : double;
{
  a_n(x)/a_n'(x)
}
var
  x,y : double;
  k : integer;
begin
  y := a; x := 1;
  for k := 1 to n-1 do
  begin
    x := 1 - k*x/sqr(y);
    y := a + k/y;
  end;
  quotient := (a + n/y - y)/(1 - n*x/sqr(y) - x);
end;

procedure main(M : integer; var a : double);
{
  Newton-Raphson algorithm
}
var
  x,y : double;
begin
  x := a;
  while true do
  begin
    y := x;
    x := x - quotient(M,x);
    if abs(y - x) < 1.E-12 then Break;
  end;
  a := x;
end;

procedure test(M : integer);
var
  a,vgl : double;
  k : integer;
begin
  a := 1;
  for k := 2 to M do
  begin
    main(2*k,a); vgl := 4/(a*a*a);
    Writeln(a,' ',2*k,',',2*k+1,' ',vgl);
  end;
end;

begin
  test(4999);
end.

I leave it up to the interested user to figure out the inner workings of this little program. Especially note that the quotient of $a_n(a)$ and its derivative $a_n'(a)$ can be calculated iteratively, in one sweep.

Upon request: A graph showing the (numerically obtained) intersection points (abscissas) as a function of $n$ would be nice :) But instead, here comes a graph of ( the natural logarithm of ) the number of iterations $n$ as a function of the abscissas $a$ of the intersection points, where $0 < a < 1$ and $0 < \ln(n) < 15$ . And $10,000$ intersection points have been taken into account.

Solution 2:

Here is an answer which proves that the conjecture holds for $a > 1$. For the general case I couldn't show it but I present some ideas.

The proof follows by induction. We want $a_{n+1} > a_n$. So we need (see the calculations by Han de Bruijn):

$$ a_n < \frac{a}{2} + \sqrt{\left(\frac{a}{2}\right)^2+n} = U(n) $$

So this constitutes an upper bound $U(n)$ for all $a_n$. Since this must hold for all $a_n$, we can ask for a condition for this to hold for $a_{n+1}$. We get

$$ a + \frac{n}{a_n} = a_{n+1} < \frac{a}{2} + \sqrt{\left(\frac{a}{2}\right)^2+n+1} = U(n+1) $$

which gives (SOME MORE STEPS ADDED HERE by request) $$ a_{n} > \frac{n}{- {a} + U(n+1) } = \frac{n}{n+1} U(n+1) $$

The latter equality can be verified by clearing denominators:

$$ n+ 1 = {- {a} U(n+1) } + (U(n+1))^2 $$ inserting $U(n+1)$

$$ n+ 1 = - {a} \left[\frac{a}{2} + \sqrt{\left(\frac{a}{2}\right)^2+n+1} \right] + \left[\frac{a}{2} + \sqrt{\left(\frac{a}{2}\right)^2+n+1} \right]^2 $$ and expanding the brackets: $$ n+ 1 = - \frac{a^2}{2} - a \sqrt{\left(\frac{a}{2}\right)^2+n+1} + \frac{a^2}{4} + a \sqrt{\left(\frac{a}{2}\right)^2+n+1} + \left(\frac{a}{2}\right)^2+n+1 $$ which clearly is an identity. (END EDIT)

Summarizing, we have $$ a_n > \frac{n}{n+1} \left[\frac{a}{2} + \sqrt{\left(\frac{a}{2}\right)^2+n+1} \right] = \frac{n}{n+1} U(n+1) = L(n) $$

So this constitutes a lower bound $L(n)$ for all $a_n$. By induction, if for some $N$, $L(N) < a_N < U(N)$, then these lower and upper bounds are necessary conditions for all further $n > N$ in order that $a_{n+1} > a_n$.

Now we give a (further) sufficient condition for that to hold. The idea is to show that for any $a_n$ with $L(n) < a_n < U(n)$, also $L(n+1) < a_{n+1} < U(n+1)$ holds. Since $a_{n+1} = a + \frac{n}{a_n}$, we have that 1) the highest $a_{n+1}$ will be obtained from the lowest $a_{n} = L(n)$ and 2) the lowest $a_{n+1}$ will be obtained from the highest $a_{n} = U(n)$.

So we need for 1) $$ a + \frac{n}{L(n)} \leq U(n+1) $$

and for 2) $$ a + \frac{n}{U(n)} \geq L(n+1) $$

Establishing this, we have, by induction, that all $a_n$ will always stay within the limits $L(n) < a_n < U(n)$ and hence we have proved the OP's claim.

For 1): Inserting $L(n)$ and $U(n+1)$ gives

$$ a + \frac{n}{\frac{n}{n+1} U(n+1)} \leq U(n+1) $$

Solving this for $U(n+1)$ gives $$ U(n+1) \geq \frac{a}{2} + \sqrt{\left(\frac{a}{2}\right)^2+n+1} $$ which holds by the definition of $U(n)$.

For 2): Inserting $L(n+1)$ and $U(n)$ gives

$$ a + \frac{n}{U(n)} \geq \frac{n+1}{n+2} U(n+2) $$

The LHS equals $U(n)$ (clear by inserting it). Then we need $$ {U(n)} \geq \frac{n+1}{n+2} U(n+2) $$

Inserting $U(n)$ and doing the algebra gives $$ a \sqrt{\left(\frac{a}{2}\right)^2+n} > 1 - \frac{a^2}{2} $$ Clearly, for $a > 1$ this holds. For $a < 1$ we can square and get $$ a^2 \left(\frac{a}{2}\right)^2+ n a^2 > \frac{a^4}{4} + 1 - a^2 $$ or $$ n > \frac{1}{a^2} -1 $$

Let's first look at the case $a > 1$. This gives for $n=1$ (start of induction) that $ \frac12 \left[\frac{a}{2} + \sqrt{\left(\frac{a}{2}\right)^2+2} \right] = L(1) < a_1 < U(1) = \frac{a}{2} + \sqrt{\left(\frac{a}{2}\right)^2+1}$

Since $a_1 = a$ by the task description, we must have that $ \frac12 \left[\frac{a}{2} + \sqrt{\left(\frac{a}{2}\right)^2+2} \right] < a < \frac{a}{2} + \sqrt{\left(\frac{a}{2}\right)^2+1}$

The right inequality is obvious and the left inequality holds for $a > 1$. This establishes my first claim that the OP's conjecture holds for $a > 1$.

As for $a <1$, in this case we have that the initial condition $a_1=a$ violates the lower bound $L(1)$. Further, our sufficient (conservative) condition will only be satisfied for $ n > \frac{1}{a^2} -1 $.

If we require, as in the original setting, $n > \frac{4}{a^3}$, then for $a <1$, the condition $ n > \frac{1}{a^2} -1 $ will be satisfied anyway. So the program of proof could be: show that, if we start with $a_1 = a$, and take $N = \frac{4}{a^3}$ many iteration steps $a_{n+1} = a + n/a_n$, then $L(N) < a_N < U(N)$. From this the general proof would follow.

Solution 3:

This is NOT an answer, but an observation that could perhaps be a relevant input to finding an answer. I'll be using naive math methods in the following and there's probably a simple reason for the observation, but I thought it was interesting enough to dare make a non-answer.

From numerical calculations it seems that $a_n$ tends to $\sqrt n + \frac{a}{2}$ for large $n$. I.e it seems to tend to a function of $n$ and $a$ which we will call $f(n,a)$. Let us further assume that for large $n$ we have $a_{n+1} \approx a_n$. We can then change the original sequence in the following way: $$a_{n+1}=a+\frac{n}{a_n}$$

becomes $$a_n*a_{n+1}=a*a_n+n$$

which becomes $$f(n,a)^2 \approx a*f(n,a)+n$$

Solving this equation we find that $$f(n,a) \approx \frac{a+\sqrt{a^2+4*n}}{2}$$

(For large $n$ we see this reduces to $f(n,a) \approx \sqrt n + \frac{a}{2}$, which was our original inkling).

Anyway, here comes the interesting bit. If we now calculate the difference between $a_{n}$ and $f(n,a)$, we find that this difference switches between a greater than $0$ difference and a less than or equal to $0$ difference for all $n \lt \frac{4}{a^3}$!! After this, the difference remains positive.

Not sure this helps, but I found it interesting.

Edited to add

After further simulations I can see that my claim in the last (but one) paragraph is not true. In fact, the end of the switching between positive and negative differences exibited by $a_n-f(n,a)$ seems a better lower bound than $n \lt \frac{4}{a^3}$. As an example, take $a=0.2$. The conjecture says $a_{n+1} \gt a_n$ when $n \lt \frac{4}{0.2^3} = 500$, but in fact $a_{n+1} \gt a_n$ already at $n = 409$ which is exactly where the switching between positive and negative differences stop.