There is a cool little proof by Wai Yan Pong titled Sums of Consecutive Integers. Here is a slightly longer way of saying the same thing (this is basically the thought process I went through to understand the Pong proof). TerminologyWe will call a consecutive series of counting numbers that sums to n a "decomposition" of n. If the decomposition has m members, we will say that the decomposition is of length m.
We will call the number n itself the "trivial decomposition" of n. That is, n = n, and n is a series of counting numbers of length 1. QuestionWhat counting numbers have no decomposition other than the trivial decomposition? We will proceed by showing that (1) a decomposition of n can be constructed using a procedure that starts with an odd factor of n. Next, we will prove that (2) every decomposition of n can be constructed this way. Finally, we will observe that (3) for odd factors greater than 1, the constructed decomposition will have a length greater than 1. Therefore, (4) the counting numbers that have no decomposition other than the trivial decomposition are the counting numbers that have no odd factors other than 1, a.k.a. the powers of 2. Proof(1) Every odd factor k of counting number n is associated with a decomposition of n.You might we wondering why one would try to construct decompositions of n that are associated with odd factors. Consider an odd factor k of counting number n. This means there is some counting number m such that mk = n. Let us now consider the series of k consecutive integers that is centered on m. There will be (k-1)/2 integers on each side of m, so our series is:By design, the sum of this series is mk = n. This means that if m-(k-1)/2 is positive, the series is a consecutive series of counting numbers that sums to n, which would make the series a decomposition of n. For example, if we are looking for a decomposition of 75, we might consider the odd factor 5, and then construct the series of 5 consecutive integers centered on 15, which is 13, 14, 15, 16, 17. This series sums to 75, and all of the numbers in the series are counting numbers, hence the series is a decomposition of 75.So this suggests that odd factors are an interesting place to start when looking for decompositions. But sometimes m-(k-1)/2 will not be positive. For example, let us again assume we are looking for a decomposition of 75. Instead of considering the odd factor 5, we might consider the odd factor 15. We then would construct a series of 15 consecutive integers centered on 5, which is -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. This series sums to 75, but it has a lot of numbers that aren't counting numbers. It turns out that there is a way to fix this problem: We can eliminate the first several members of the series that together sum to 0, which is to say, eliminate the negative numbers, the 0, and the additive inverses of the eliminated negative numbers, leaving 3, 4, 5, 6, 7, 8, 9, 10, 11, 12:
Because the eliminated numbers sum to 0, the remaining series still sums to 75, and all of the numbers in this series are counting numbers, so we still have a decomposition of 75. Generalizing, if m-(k-1)/2 is not positive, we remove this sub-series:
which is a decomposition of n. The removed sub-series has -2 (m-(k-1)/2) + 1 terms, which simplifies to -2m+k, and thus the decomposition has a length of 2m, which is also 2n/k. Either way, starting with an odd factor, we have constructed a decomposition of n, which we will call the decomposition of n associated with k. It is interesting (and hopefully now fairly intuitive) that we can construct a decomposition of n using the odd factors of n. But might there are some decompositions of n that cannot be created this way? As it turns out the answer is "no." We will show this to be the case by starting with an arbitrary decomposition of n and then will show that there is an odd factor of k with which this decomposition is associated. We will call our arbitrary decomposition D. This decomposition starts with some counting number a and is of length j:
We will show that this is precisely the decomposition of n associated with some odd factor k. Because D is a decomposition of n, this means:
The right side of that equation has j terms, and the average of the terms is (a + a+j-1)/2. Thus:
If j is odd, this means j is an odd factor of n. If j is even, then j/2 is a whole number, which means (2a+j-1) is a factor of n. And because j is even, it follows that (2a+j-1) is odd. Let us consider both possibilities, and verify that in either case, the decomposition of n associated with whichever of those is an odd factor of n is in fact the decomposition D. (2a) If j is odd, then the decomposition of n associated with j is D. Consider the case where j is odd. Let us construct the decomposition associated with j. Thus, k = j, and m = (2a+j-1)/2. We then construct this series: Is the first term of that series positive? (2b) If j is not odd, then (2a+j-1) is odd, and then the decomposition of n associated with (2a+j-1) is D. Now consider the other case, where j is even. If so, then (2a+j-1) is odd. Let us construct the decomposition associated with (2a+j-1). Thus, k = (2a+j-1), and m= j/2. We then construct this series: Is the first term of that series positive?
Because a is a counting number, this means -a+1 is not positive. We therefore know that the decomposition of n associated with (2a+j-1) begins with the term (k-1)/2-m+1:
We also know that the decomposition of n associated with (2a+j-1) has a length of 2n/(2a+j-1). Because n = j(2a+j-1)/2, it follows that 2n/j = 2a+j-1, and thus that 2n/j-j+1 = 2a. Substituting for 2a yields:
Therefore, if j is even, the decomposition of n associated with (2a-j-1) starts with a and has length j, which is D. Thus, not only is it true that every odd factor of n can be used to construct a decomposition of n, it also is true that every decomposition of n is associated with an odd factor of n. Recall that the decomposition of n associated with k is either of length k or 2m. This means that the decomposition of n always has a length > 1 if k > 1. That is, any counting number n with an odd factor other than 1 has a non-trivial decomposition! And the counting numbers with no odd factors other than 1 are the powers of 2 (because all prime numbers other than 2 are odd, and thus all counting numbers other than powers of 2 have odd factors). Moreover, for n = a power of 2, n has only one odd factor, 1, and that odd factor is associated with the trivial decomposition. Thus, powers of 2 never have a non-trivial decomposition. (4) Therefore:
|