Exercise 1.3.37* (Sweeping generalization.)

Question

Prove that in any block of consecutive positive integers there is a unique integer divisible by a higher power of $2$ than any of the others. Then use this, or any other method, to prove that there is no integer among the $2^{n+1}$ numbers
$$\pm\frac{1}{k}  \pm\frac{1}{k+1} \pm\frac{1}{k+2} \pm\cdots \pm \frac{1}{k+n}.$$
(Note that this result is a sweeping generalization of the preceding problem.)

Richard Ganaye · Accepted Answer

ewcommand{\Q}{\mathbb{Q}} ewcommand{\Z}{\mathbb{Z}} ewcommand{\N}{\mathbb{N}} ewcommand{\R}{\mathbb{R}} Notations : \begin{itemize} \item $\N = \{0,1,2,3,\ldots\}$, set of natural numbers. \item $ [\![a,b]\!] =\{ x \in \N \mid a \leq x \leq b\},\qquad (a,b \in \N)$. \item $ k = u_2(n) \iff (2^k \mid n, 2^{k+1} mid n), \qquad (k,n \in \N)$. \end{itemize} \begin{proof} A block of four consecutive integers contains always a multiple of $4$. A block of $6$ consecutive integers contains one or two multiples of 4, and in the last case, one of them is a multiple of $8$. We generalize these remarks in the following lemma. \bigskip {\bf Lemma.} Let $k,n \in \N$, where $n>1$. Consider a block $I = [\![k,k+n-1]\!]$ of $n$ consecutive numbers, and define $m$ as the only integer $m \in \N$ such that $2^m \leq n < 2^{m+1}$. Then \begin{enumerate} \item[(i)] The block $I$ contains one or two multiples of $2^m$. In the last case one of them is a multiple of $2^{m+1}$, but not both. \item[(ii)] Let $2^l$ be the higher power of $2$ that divides some integer of $I$. Then there is only one $i \in I$ such that $2^l$ divides $i$, i.e. \begin{align*} 2^l \mid i & ext{ for some }i\in [\![k,k+n-1]\!] ,\ 2^{l} mid j& ext{ for every } j \in [\![k,k+n-1]\!], j e i. \end{align*} \end{enumerate} \begin{proof} (of lemma) \begin{enumerate} \item[(i)] We first show that $I$ contains at least one multiple of $2^m$. Since $2^m \leq n$, the block $I$ contains the block $J = [\![k,k+2^m -1]\!] $ of $2^m$ consecutive numbers. There is one an only one $ r\in \Z$ such that $$r \equiv -k \mod{2^m},\qquad 0 \leq r < 2^m$$ ($r$ is the remainder of the Euclidean division $-k = 2^m q +r,\ 0 \leq r < 2^m$, of $-k$ by $2^m$). Then $ i = k+r \in J \subset I$ is a multiple of $2^m$, so $I$ contains a multiple of $2^m$. Now we show that $I$ contains at most two multiples of $2^m$. Let $ 2^mu \leq 2^mv$ be multiples of $2^m$ in $I$. Then $$k \leq 2^m u \leq 2^m v < k+n.$$ Then $0 \leq 2^m (v -u) < n <2^{m+1},$ therefore $0 \leq v-u < 2$, so that $v = u$ or $v = u+1$. This proves that $I$ contains at most two multiples of $2^m$. If $I$ contains two such multiples, then $v = u+1$, thus $u$ or $v$ is even. This shows that $ 2^mu$ or $2^mv$ is a multiple of $2^{m+1}$, but not both. \item[(ii)] If there is exactly one integer $i$ in $I$ such that $2^m \mid i$, then $l = u_2(i) \geq m$, and $ u_2(j) < m$ if $j \in I, j e i$. In this case $2^l$ is the higher power of $2$ that divides some integer of $I$, and $i$ is the only integer in $I$ such that $2^l \mid i$. If there are two multiples $i,j$ of $2^m$ in $I$, one of them, say $i$, is a multiple of $2^{m+1}$, but not $j$, and $l= u_2(n)\geq m+1$. In this case $2^l$ is the higher power of $2$ that divides some integer of $I$, and $i$ is the only integer in $I$ such that $2^l \mid i$. \end{enumerate} \end{proof} If $n = 1$, the block $\{1\}$ gives a sum $\pm \frac{1}{1}$ which is an integer, and the block $\{k\}$, where $k>1$ gives a sum $\pm\frac{1}{k}$ which is not an integer. Assume now that $n>1$. We prove that there is no integer among the $2^n$ numbers $$S = \varepsilon_0\frac{1}{k} + \varepsilon_1\frac{1}{k+1} + \varepsilon_2\frac{1}{k+2}+ \cdots + \varepsilon_{n-1} \frac{1}{k+n-1},$$ where $\varepsilon_0,\varepsilon_1,\ldots,\varepsilon_{n-1} \in \{-1,1\}$. (This is equivalent to the sentence, if we replace $n-1$ by $n$). Let $2^l$ be the higher power of $2$ that divides some integer of $I = [\![k,k+n-1]\!] $. Since $n>1$, we know that $l\geq 1$. By the Lemma, \begin{align} 2^l \mid k+i & ext{ for some }i\in [\![0,n-1]\!] , \qquad 2^{l+1} mid k+i\ 2^{l} mid k+j& ext{ for every } j \in [\![0,n-1]\!], j e i. \end{align} The reduction of $S$ to the same denominator gives $S = N/D$, where \begin{align*} D &= k(k+1)\cdots(k+n-1) = \frac{(k+n-1)!}{(k-1)!} \in \N,\ N &= \sum_{j = 0}^{n-1} \varepsilon_jn_j,\qquad ext{where}\ n_j&=\frac{k(k+1)\cdots(k+n-1)}{k+j} = \frac{(k+n-1)!}{(k-1)!(k+j)}\in \N\qquad (j=0,\ldots,n-1). \end{align*} Define $K = u_2(D) = u_2\left( \frac{(k+n-1)!}{(k-1)!} ight)$. For all $j \in [\![0,n-1]\!] $, \begin{align*} j e i \ \Rightarrow\ & u_2(n_j) = u_2(D) - u_2(k+j) \geq K - l + 1,\ & u_2(n_i) = u_2(D) - u_2(k+i) = K-l. \end{align*} Hence $2^{K-l+1}$ divides all $n_j$, except $n_i$, and $2^{K-l}$ divides $n_i$. Thus $$2^{K-l} \mid N, ext{ but } 2^{K-l+1} mid N,$$ so $$N = 2^{K-l} N', ext{ where } 2 mid N'.$$ By the definition of $K$, $2^K \mid D$. Because $l\geq 1$, a fortiori $2^{K-l+1} \mid D$, so that $D = 2^{k-l+1}D'$. Dividing $N$ and $D$ by $2^{K-l}$, we obtain $$S = \frac{N}{D} = \frac{N'}{2D'}.$$ If $S$ is an integer, then $N' = 2SD'$ is even, and this is a contradiction, since $2 mid N'$. So $S$ is never an integer (except when $n=k=1$). \end{proof}

Exercise 1.3.37* (Sweeping generalization.)

Answers

Comments

Exercise 1.3.37* (Sweeping generalization.)

Answers

Comments

Add answer