0
$\begingroup$

Let $a_n = \left[\sqrt{(n+1)^2+n^2}\right], n = 1,2,\ldots,$ where $[x]$ denotes the integer part of $x$. Prove that

$\quad$ (a) there are infinitely many positive integers $m$ such that $a_{m+1}-a_{m} > 1$;

$\quad$ (b) there are infinitely many positive integers $m$ such that $a_{m+1}-a_m = 1$.

If $a_{m+1} \geq a_m+1$, then if $k^2 \leq 2m^2+2m+1 < (k+1)^2 \implies k < 2m$, then $$(k+1)^2 \leq 4m^2.$$

How can we continue this approach or is there another way (I saw another way using Pell equations)?

$\endgroup$
2
$\begingroup$

A famous fact about binomial coefficients is: $$\binom{n}{2}\text{ is a perfect square for infinitely many } n.$$ This statement can be proved without Pell's equation, in the following way: $$\binom{(2n-1)^2}{2}=(2n-1)^2\cdot2n(n-1)$$ and if $\binom{n}{2}$ is a perfect square, the above expression is another perfect square. Now note that $\binom{9}{2}=6^2$.

Thus we may take $m=n-2$ where $\binom{n}{2}$ is a perfect square and finish the proof of (a).
(b) is trivial.

$\endgroup$
  • $\begingroup$ How does this prove part (a)? $\endgroup$ – user19405892 Jul 29 '16 at 2:11
  • $\begingroup$ @user19405892 Suppose $n(n-1)=2k^2$. One may immediately check that $a_{n-1}=2k$ and $a_{n-2}\leq 2k-2$(This inequality is done by a plain estimation $n>k+1$). $\endgroup$ – Cave Johnson Jul 29 '16 at 2:16
  • $\begingroup$ Can you explain how to get $a_{n-2} \leq 2k-2$? How do you know $n > k+1$? $\endgroup$ – user19405892 Jul 29 '16 at 2:23
  • $\begingroup$ If $n\leq k+1$ then $n(n-1)\leq k(k+1)<2k^2$, a contrdiction. So $\sqrt{(n-1)^2+(n-2)^2}=\sqrt{2n(n-1)-4n+5}<\sqrt{4k^2-4(k+1)+5}=2k-1$. $\endgroup$ – Cave Johnson Jul 29 '16 at 2:31
  • $\begingroup$ How do we prove (b)? $\endgroup$ – user19405892 Jul 29 '16 at 2:35
1
$\begingroup$

Here is a proof sketch. First we show that $a_{m+1} - a_m$ can never be zero. This is because $(n+1)^2 + n^2$ increases by $4n + 4$ when $n$ increases by $1$. But, consecutive squares near $(n+1)^2 + n^2$ are closer together than this. (They are roughly $2 \sqrt{2} n$ apart). So $\sqrt{(n+2)^2 + (n+1)^2}$ and $\sqrt{(n+1)^2 + n^2}$ differ by more than one, and their floors cannot be the same.

Next, assume (a) is false. There are only finitely many $m$ such that $a_{m+1} - a_m > 1$, so let $n$ be the largest one. For any $m > n$, $a_{m+1} = a_m + 1$. This means, for instance, $a_{2n} - a_n = n$. But the difference between $\sqrt{(n+1)^2 + n^2}$ and $\sqrt{(2n + 1)^2 + (2n)^2}$ is roughly $n\sqrt{2}$; it is too big for the difference of the floors to be $n$.

Similarly, assume (b) is false. Now we can say for any $m > n$, $a_{m+1} \ge a_m + 2$. So $a_{2n} - a_n \ge 2n$. The difference of floors of square roots cannot be this large when the difference of square roots directly is, as above, roughly $n\sqrt{2}$.

$\endgroup$

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.