Prove conjecture $a_{n+1}>a_{n}$ if $a_{n+1}=a+\frac{n}{a_{n}}$ Let sequence $\{a_{n}\}$ such $a_{1}=a>0$,and 
$$a_{n+1}=a+\dfrac{n}{a_{n}}$$
I used the software to find this following conjecture :
if $n>\dfrac{4}{a^3}$,we have 
$$a_{n+1}>a_{n}$$
 A: 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.
A: 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. 
A: A really interesting observation (thanks to @HanDeBruijn's for revealing the pattern) that can lead to a solid proof:
$$a_n=\frac{P_n(a)}{P_{n-1}(a)}$$
where $P_n(a)=a^n+...$ - is a polynomial of $a$ and degree $n$ with all the coefficients being integers and greater than $0$ (leading one is $1$), because:


*

*$a_1=\frac{a}{1}=\frac{P_1(a)}{P_0(a)}$

*$a_2=\frac{a^2+1}{a}=\frac{P_2(a)}{P_1(a)}$

*$a_3=\frac{a^3+3a}{a^2+1}=\frac{P_3(a)}{P_2(a)}$

*by induction $$a_{n+1}=a+\frac{n}{\frac{P_n(a)}{P_{n-1}(a)}}=\frac{aP_n(a)+nP_{n-1}(a)}{P_n(a)}=\frac{P_{n+1}(a)}{P_n(a)}$$ because $aP_n(a)$ is already of degree $n+1$.


One extra observation is that if $$P_n(a)=a^n+c_{n,n-1}a^{n-1}+c_{n,n-2}a^{n-2}+Q_{n-3}(a)$$
$Q_{n-3}(a)$ is just a polynomial of degree $n-3$, then
$$P_{n+1}(a)=aP_n(a)+nP_{n-1}(a)=(a^{n+1}+c_{n,n-1}a^{n}+c_{n,n-2}a^{n-1}+aQ_{n-3}(a))+\\n(a^{n-1}+c_{n-1,n-2}a^{n-2}+c_{n-1,n-3}a^{n-3}+Q_{n-4}(a))=\\a^{n+1}+c_{n,n-1}a^{n}+(c_{n,n-2} + n)a^{n-1}+\left(aQ_{n-3}(a) + nc_{n-1,n-2}a^{n-2}+nc_{n-1,n-3}a^{n-3}+nQ_{n-4}(a)\right)=\\a^{n+1}+c_{n+1,n}a^{n}+c_{n+1,n-1}a^{n-1}+...$$
and, very important:
$$c_{n,n-1}=c_{n+1,n}$$
$$c_{n+1,n-1}=c_{n,n-2} + n$$
Then from $$a_{n+1}-a_n=\frac{P_{n+1}(a)}{P_{n}(a)} - \frac{P_{n}(a)}{P_{n-1}(a)}=\frac{P_{n+1}(a)P_{n-1}(a)-P_{n}(a)^2}{P_{n}(a)P_{n-1}(a)}$$
we have
$$a_{n+1}>a_n \Leftrightarrow P_{n+1}(a)P_{n-1}(a)>P_{n}(a)^2$$
But
$$P_n(a)^2=a^{2n}+2c_{n,n-1}a^{2n-1}+\left(c_{n,n-1}^2 + 2c_{n,n-2}\right)a^{2n-2}+...$$
and
$$P_{n+1}(a)P_{n-1}(a)=a^{2n}+\left(c_{n-1,n-2}+c_{n,n-1}\right)a^{2n-1}+\\ \left(c_{n-1,n-3}+c_{n,n-1}c_{n-1,n-2}+c_{n,n-2}+n\right)a^{2n-2}+...$$
Considering the very important note above, this is:
$$P_{n+1}(a)P_{n-1}(a)=a^{2n}+2c_{n,n-1}a^{2n-1}+\\ \left(c_{n-1,n-3}+n-1+c_{n,n-1}^2+c_{n,n-2}+n - (n-1)\right)a^{2n-2}+...=\\a^{2n}+2c_{n,n-1}a^{2n-1}+\left(c_{n,n-2}+c_{n,n-1}^2+c_{n,n-2}+1)\right)a^{2n-2}+...=\\a^{2n}+2c_{n,n-1}a^{2n-1}+\left(c_{n,n-1}^2+2c_{n,n-2}+1\right)a^{2n-2}+...$$
So, we see that 
$$P_{n+1}(a)P_{n-1}(a) - P_n(a)^2 = a^{2n-2}+...$$
which from some $a$ becomes always positive.
