Exercise 1.3.40* (Which natural numbers are sums of consecutive integers ?)

Question

Say that a positive integer $n$ is a sum of consecutive integers if there exist positive integers $m$ and $k$ such that
$$n = m + (m+1)+ \cdots + (m+k).$$
Prove that $n$ is so expressible if and only if it is not a power of $2$.

Richard Ganaye · Accepted Answer

\begin{proof} If $n$ is a sum of consecutive integers, then
\begin{align*}
n &= \sum_{i=0}^k(m+i) \
&= \sum_{j=0}^k (m+k-j)\qquad (	ext{where } j = k-i)\
&= \sum_{i=0}^k  (m+k-i).
\end{align*}Therefore
$$2n =  \sum_{i=0}^k(m+i) +  \sum_{i=0}^k(m+ k-i) = \sum_{i=0}^k (2m+k) = (k+1)(2m+k)$$
(Gauss' trick). So
$$n = \frac{(k+1)(2m+k)}{2} \qquad (m>0, k>0).$$

\medskip
We prove first that a power of $2$ is not so expressible. If $2^u = \frac{(k+1)(2m+k)}{2}$, then
$$2^{u+1} = (k+1)(2m+k).$$
If $k$ is even, then $k+1$ is odd (and $k+1 \geq 2$), and if $k$ is odd, then $2m +k$ is odd (and $2m+k \geq 2$). In both cases $2^{u+1}$ has an odd divisor greater that $1$. This is impossible because the only  divisors of $2^{u+1}$  greater than $1$ are powers of $2^i$, where $i\geq 1$, so are all even.
\end{proof}

Take now $n>1$ which is not a power of $2$. The decomposition of $n$ in prime factors is
$$n = 2^{r} p_2^{a_2}\cdots p_l^{a_l},$$
where $p_2^{a_2}\cdots p_l^{a_l}$ is odd and greater that $1$ (otherwise $n$ is a power of $2$). Thus

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

$$2n = 2^r (2s+1),\qquad r> 0, s>0.$$

Consider two cases.
\begin{itemize}
\item If $2^{r-1} > s$, then define
$$k = 2s >0,\qquad m =2^{r-1} -s >0.$$
Then 
\begin{align*}
2n &= (2s + 1) 2^r\
&= (k+1) (2^r - 2s + 2s)\
&=(k+1)(2m +k),\
\end{align*}
so $n =\frac{(k+1)(2m+k)}{2} = \sum_{i=0}^k (m+i) \ 	ext{ where } k>0,m>0$, is a sum of consecutive integers.
\item If $2^{r-1} \leq s$, then define
$$k = 2^r - 1>0, \qquad m = s + 1 -2^{r-1} >0.$$
Then $2m + k= 2s + 2 - 2^r + 2^r - 1 = 2s + 1$, thus
\begin{align*}
2n &= 2^r(2s+1)\
&=(k+1)(2m+k)
\end{align*}
so $n =\frac{(k+1)(2m+k)}{2} \ (k>0,m>0)$ is a sum of consecutive integers.
\end{itemize}
In both cases, $n$ is a sum of consecutive integers.

$n$ is a sum of consecutive integers if and only if $n$ is not a power of $2$.

Exercise 1.3.40* (Which natural numbers are sums of consecutive integers ?)

Answers

Comments

Exercise 1.3.40* (Which natural numbers are sums of consecutive integers ?)

Answers

Comments

Add answer