Let $\, k_1 < k_2 < k_3 < \cdots \,$ be positive integers, no two consecutive, and let $\, s_m = k_1 + k_2 + \cdots + k_m \,$ for $\, m = 1,2,3, \ldots \; \;$. Prove that, for each positive integer $\, n, \,$ the interval $\, [s_n, s_{n+1}) \,$ contains at least one perfect square.
Problem
Source: USAMO1994
Tags: LaTeX, number theory unsolved, number theory
22.08.2005 16:54
We notice that $s_n = k_1 + k_2 + \ldots + k_n \geq 1 + 3 + \ldots + (2n-1) = n^2$. If $s_n = m^2$ for some $m \in \mathbb{Z}^+$, then we are done. If not, then letting $r$ be the largest non-negative integer such that ${(n+r)}^2 < s_n$, we note that the next perfect square ${(n+r+1)}^2$, which is $2n+2r+1$ greater than ${(n+r)}^2$. We now claim that this difference $2n+2r+1$ is $\leq k_{n+1}$. To see this, we suppose not, then we have $2n+2r+1 > k_{n+1} \Rightarrow 2n+2r \geq k_{n+1} \Rightarrow 2n+2r-2 \geq k_n$ $\Rightarrow k_n+k_{n-1} + \ldots + k_1 \leq (2n+2r-2) + (2n+2r-4) + \ldots + 2r = n^2 + 2nr -n$, which is less than $n^2 + 2nr + r^2 = {(n+r)}^2$. (Contradiction, since we have assumed that $s_n = k_1 + k_2 + \ldots + k_n > {(n+r)}^2$.) Thus ${(n+r+1)}^2 \in [s_n, s_{n+1})$ and we are done.
23.08.2005 18:54
$n(x_{n+1}-1)>=s_n+n^2>=2n\sqrt{s_n}$ so $x_{n+1}>=2\sqrt{s_n}+1$ and $s_{n+1}>=(\sqrt{s_n}+1)^2$ so we get$ \sqrt{s_{n+1}}-\sqrt{s_n}>=1$ so the interval contains a square.
01.09.2005 11:59
dblues wrote: Erm... I believe you mean the interval $[sn, s(n+1) )$, or rather $[s_n, s_{n+1})$. The second one
02.09.2005 19:19
Makaveli wrote: dblues wrote: Erm... I believe you mean the interval $[sn, s(n+1) )$, or rather $[s_n, s_{n+1})$. The second one Well... if i've already solved the problem, it just means i definitely know it's the second one. You originally wrote $[sn, sn+1)$ without latex, which is not what you mean. I'm just trying to say that even without latex, u should write $[sn, s(n+1) )$ instead, so that we can interpret it as $[s_n, s_{n+1})$. Best thing is to go latex of course.
14.04.2009 01:12
Can't we prove this using the argument that perfect squares have differences of consecutive odds, and the interval with width $ s_m$ are larger than these odd numbers (because the base case of the sequence is 1,3,5,7,..., and every other sequence either has the same interval width or a larger one), i.e. proving the base case and then proving that it would work for any case greater than the base case?
14.04.2009 01:28
that is essentially what dblues did.
14.04.2009 02:19
gauss202 wrote: that is essentially what dblues did. thanks, i read through his proof once more, and i see it now.
28.02.2010 01:16
Note that $ s_{n + 1} - s_n = k_{n + 1} \ge k_{n} + 2$. Also, $ s_n \le k_n + (k_n - 2) + (k_n - 4) + ......$($ 2$ or $ 1$)$ = (\frac {k_n + 1}{2})^2$ if $ k_n$ is odd and $ \frac {k_n^2 + 2k_n}{4}$ if $ k_n$ is even. In either case, $ s_n \le (\frac {k_n + 1}{2})^2$. But then the greatest possible difference between $ s_n$ and the next square number after $ s_n$ must be $ (\frac {k_n + 3}{2})^2 - (\frac {k_n + 1}{2})^2 = k_n + 2$, and since the difference between $ s_{n + 1}$ and $ s_n$ is at least this, there must be a square on the interval $ [s_n,s_{n + 1})$.
05.04.2012 23:21
Dear Friends I solved it by Apriority( if I used the right word!) 1.it's also clear that between $K$ and $K'$ which $K\leq K+2$ there is a square.by using what dear dgreenb801 said. 2.we assumed that for integer $m$, between $s_{m}$ and $s_{m+1}$ there is atleast one square. 3.we'll prove that between $s_{m+1}$ and $s_{m+2}$ there is atleast one square. 4.and it's Done. also the third step proved by what dear dgreenb801 said. With Regards.
30.12.2018 22:19
dgreenb801 wrote: Note that $ s_{n + 1} - s_n = k_{n + 1} \ge k_{n} + 2$. Also, $ s_n \le k_n + (k_n - 2) + (k_n - 4) + ......$($ 2$ or $ 1$)$ = (\frac {k_n + 1}{2})^2$ if $ k_n$ is odd and $ \frac {k_n^2 + 2k_n}{4}$ if $ k_n$ is even. In either case, $ s_n \le (\frac {k_n + 1}{2})^2$. But then the greatest possible difference between $ s_n$ and the next square number after $ s_n$ must be $ (\frac {k_n + 3}{2})^2 - (\frac {k_n + 1}{2})^2 = k_n + 2$, and since the difference between $ s_{n + 1}$ and $ s_n$ is at least this, there must be a square on the interval $ [s_n,s_{n + 1})$. If $s_{n+1}\le (\frac {k_n + 1}{2})^2$ then your conclusion is incorrect.
05.11.2020 17:32
Consider a particular $n$. Say that $k^2< s_n\le (k+1)^2$ for some integer $k$. Suppose for contradiction that $[s_n,s_{n+1})$ does not contain at least one perfect square, then $s_{n+1}\le (k+1)^2$, so $s_{n+1}-s_n=k_{n+1}\le 2k$. This implies that $s_n$ is at most \[(2k-2)+(2k-4)+\cdots+2 = 2\cdot \frac{k(k-1)}{2} = k(k-1),\]contradiction.