1
$\begingroup$

In this equation: $\sqrt{1+2x(x-1)} = K$, $K$ is an integer constant, I need to check if there exists integer $x$ satisfying this equation. Can anyone prove some lower and upper bound for $x$. Here is how I proceeded(and failed):

Obviously: $\sqrt{2x(x-1)} \approx \sqrt{1+2x(x-1)}$

$\Rightarrow \sqrt{2x(x-1)} \approx K$

$\Rightarrow \sqrt{x(x-1)} \approx K/\sqrt{2}$

Also obvious is: $x - 1 \approx x$

$\Rightarrow x(x-1) \approx x \times x$

$\Rightarrow \sqrt{x(x-1)} \approx x$

Combining $\sqrt{x(x-1)} \approx K / \sqrt{2}$ and $\sqrt{x(x-1)} \approx x$ implies $x \approx K / \sqrt{2}$. But that doesn't give any specifig upper/lower bound.

  • 0
    @sven.hedin: That's not big, they grow quickly, we are only trying to get u_n>5\times 10^{11}. Just use the recurrence. You can also get a single second order recurrence for just $u_n$, with constant coefficients. If this does not come quickly to you I can post it. You can also get an explicit recurrence for $x_n$.2012-05-18

2 Answers 2

7

We are solving $2x^2-2x+1=K^2$ or equivalently $4x^2-4x+2=2K^2$ or equivalently $(2x-1)^2=2K^2-1$. For any explicit $K$, there are not many candidates!

If we are interested in the general theory, we might note that we are dealing here with the (negative) Pell Equation $u^2-2v^2=-1.$ There is a complete characterization of all the solutions. Let $n$ be an odd integer, and let $u_n+v_n\sqrt{2}=(1+\sqrt{2})^n$. Then $(u_n,v_n)$ is a solution, and we obtain all positive solutions in this way.

One can also get a nice explicit recurrence, with integer coefficients, for the $u_n$ and for the $v_n$. This can be derived from the fact that $u_{n+2}+v_{n+2}\sqrt{2}=(3+2\sqrt{2})(u_n+v_n\sqrt{2}).$

Alternately, let $(s_k,t_k)$ be the $k$-th positive solution of $s^2-2t^2=-1$. A bit of playing shows that each of $(s_k)$ and $(t_k)$ satisfies the recurrence $w_{k+2}=6w_{k+1}-w_k.$ The only difference is in the initial conditions.

Remark: One can find bounds, indeed exact formulas, for the $k$-th positive solution of the equation $s^2-2t^2=-1$. For if we call this $(s_k,t_k)$, then $s_k+t_k\sqrt{2}=(1+\sqrt{2})^{2k-1}$. It follows that $s_k-t_k\sqrt{2}=(1-\sqrt{2})^{2k-1}$. By adding, we find that $2s_k=(1+\sqrt{2})^{2k-1}+(1-\sqrt{2})^{2k-1}.$ One can do slightly better, by noting that $(1-\sqrt{2})^{2k-1}$ is negative, and small in absolute value. Thus $2s_k=\lfloor(1+\sqrt{2})^{2k-1}\rfloor.$ One can in a similar way obtain an explicit formula for $t_k$.

  • 1
    @sven.hedin: Just compute using one of the recurrences I have given. Our numbers grow by a factor of about $5.8$ each time. With that kind of growth, it doesn't take long to get into the range you want. Or else you can use the formula involving the exponential and greatest integer function that I added. The downside is that we then need high precision arithmetic, while for the recurrence approach it is only integer arithmetic.2012-05-19
2

Solving the quadratic gives $x = \frac{1 \pm \sqrt{2k^2-1}}{2}$. The bounds are clear from this.