[You may also want to look at the preview of the interview with Alec Klein, author of A Class Apart, to be hosted on MathNotations. Alec has agreed to answer my questions about Stuyvesant HS in NYC, other specialized schools and gifted education.]
Please comply with the 'Proper Attribution' statement that now appears in the sidebar.
Anyone recall a detailed investigation I posted in Feb '07 about numbers which can or cannot be written as a sum of 2 or more consecutive positive integers? You will probably want to quickly review that for this discussion. That investigation was implemented in a 9th grade prealgebra class with students who had struggled with math for a long time. They worked for the entire period (and into the next class as well) and expressed satisfaction and a sense of accomplishment. One student, KC, even found a way to express those numbers which were unsummable!
Today, we will take this question of which numbers are unsummable to a higher level. The challenge for my readers and for students is to use methods from Algebra 2 and basic number theory (primes, factors) to prove a conjecture made by one of my former students.
Quick background:
Students were asked to investigate those positive integers which can be written as a sum of 2 or more consecutive positive integers. I started them off with examples like
3 = 1+2; 5 = 2+3; 6 = 1+2+3, etc.
They worked in pairs and completed a table up to 36 over a couple of days. Most quickly realized that every odd positive integer starting with 3 could be represented but not every even positive integer. Working in pairs helped students to catch common arithmetic/logic errors and the results were reviewed after every 10 numbers or so in order to insure that all students had accurate results to work with.
Here's your challenge for today:
Rather than demonstrate which numbers can be represented as such a sum, your mission is to prove the following:
Powers of 2 are unsummable, i.e., a power of 2 can never be represented as a sum of 2 or more consecutive positive integers.
Notes:
(1) The whole notion of algebraic proof may be new for some students, so this may require some demonstration first.
(2) Students will need to know the formula for the sum of an arithmetic series, so this challenge would be appropriate after learning or reviewing that. The instructor however could develop that formula earlier on or simply provide the formula.
(3) Some understanding of the Fundamental Theorem of Arithmetic is needed here, i.e., every positive integer is either prime or can be written as a product of primes in a unique fashion. This theorem often goes unmentioned or taken for granted in middle school - time to bring it back?
(4) Some readers may find a way to prove this without using the algebraic formula mentioned above. Share that as well!
Enjoy...
Thursday, September 27, 2007
Taking the 'Unsummable' Numbers to a higher level: An Algebraic Proof
Subscribe to:
Post Comments (Atom)
Posts
25 comments:
Hi:
Here is an attempt.
Let M = 2^m where m is a natural number. M is even. Define M as:
M = N + n*N + n*(n + 1)/2
Where N is natural number and n represents the n number of consecutive numbers after N. So We are representing M as the sum of n + 1 consecutive integers where N is the first integer. The terms n*M + n*(n + 1)/2 represents the sum of the n integers after N.
Now we rewrite M as
2M = 2*(N + n*N) + n*(n + 1)
Now 2M is even. So is 2*(N + n*N).
But the term n*(n + 1) is ODD for any n. Since the sum of an even number and an odd number is odd this means that the even number 2*M can not be written as the sum of consecutive integers.
Hopefully I haven't left out a minor technical issue. I enjoy your blog.
Cecil, I think you're wrong in your assertion that n*(n+1) is odd for any n. (consider 6*7=42.) In fact it is even for any n, since one of n and n+1 will be odd and the other even, and odd*even is always even.
Dave, Thanks for the reminder of the unsummables (probably an excellent investigation for my middle schoolers coming off our investigation of Gauss' method of adding up arithmetic series). This is a great follow-up as well. I don't think any in my group could generate a proof, but I think they *might* enjoy seeing one. I'll let you know how it goes, if I get there. (I have so many things lined up to do with those guys!)
And here's my attempt at the proof:
Let's represent the sequence of n consecutive integers starting from a as: a + (a+1) + ... [a+(n-1)]
the sum S of that series is
S=[(2a+n-1)*n]/2
or 2S = (2a+n+1)*n
If S is a power of 2, so is 2S
Then by the fundamental theorem of arithmetic, n and 2a+n+1 must each also be powers of 2. So, n must be even. And 2a+n+1 must be even. But 2a is even and if n is even, as it must be, then 2a+n is even, and 2a+n+1 must be odd. So, 2a+n+1 and n cannot both be powers of 2. Therefore 2S is not a power of 2, and neither is S.
cecil--
I liked your version of the formula for the sum of an arithmetic series but, as mathmom showed, your argument did not quite reach a contradiction. You would need to go further:
Factoring the right side of your 2M equation:
2M = (n+1)(2N + n).
Using mathmom's reasoning with the Fundamental Theorem of Arithmetic, n+1 would have to be even, thus n would be odd. This would force the 2nd factor to be odd, a contradiction.
mathmom--
Nice!!
I certainly didn't expect middle school students to produce this on their own, but I do like the idea of showing them a mathematical proof in paragraph form. I believe we could structure this 'indirect' proof for them or perhaps give them another to try in which some of the steps are provided for them. My primary intent however was to provide secondary students with a proof activity which is not often seen beyond geometry. I'm glad you enjoyed this...
A generalization: Given a number M, what is the number of ways that it can be expressed as the sum of consecutive positive integers?
TC
tc--
Very nice! Believe it or not, I did cover some of the underlying ideas during the original activity. Students were encouraged to list the different ways to represent each positive integer. They noted that odd primes like 7 = 3+4 or 11 = 5+6 could only be represented in one way whereas numbers with many factors like 12 could be represented in more than one way. One approach is to rewrite the formula for the sum of an arithmetic series as N*M where N is the number of terms and M is the median (or mean) of these N consecutive integers. The rub is that numbers like 10 = 4*2.5 which leads to 1+2+3+4. This is a wonderful generalization, tc. Thanks!
For n consecutive integers I see:
1) symmetry (implied by consecutive)
2) a center C (implied by symmetry)
3) Sum = n * C (also implied by symmetry)
Sum = n * C cannot equal a power of 2 because:
1) when n is odd, n cannot be a factor of 2^N
2) when n is even, C = M.5 (the center is between the two "Middle" integers, implied by consecutive) and n * M.5 cannot equal 2^N
Note: symmetry is both a beautiful and powerful concept. I doubt one can get a simpler formula than Sum = n * C, yet it is quite general. It works for n = 0, for n odd or even, and only assumes symmetry (i.e. goes beyond consecutiveness and arithmetic sequences). If some of this is too cryptic, I can explain in more detail in another comment or by email (mg at primestructure dot com).
My conjecture is that the number of distinct ways that you can express a number N as the sum of consecutive positive integers is equal to the number of distinct odd factors of N, not including 1.
TC
marc--
Wonderfully intuitive approach to arithmetic sequences that is accessible (with numerical examples of course) for middle schoolers. Thanks for the contribution.
The question tc asked is also worth pursuing with middle schoolers: How do we determine the number of ways of representing each positive integer, other than powers of 2, as a sum of consecutive positive integers? Since we have to consider the M.5 possibility you raised, it's not enough to look at only integer factors of the number. Thus, 10 = 4*2.5, which leads to a sum of terms whose median is 2.5: 1+2+3+4. Thus if we were trying to represent 15 as a sum, we would need to consider 2*7.5, 6*2.5 and 10*1.5 and 30*0.5. These lead respectively to the following
representations:
7+8;
0+1+2+3+4+5;
(-3)+(-2)+(-1)+0+1+ 2+ 3+ 4+ 5 +6;
(-14)+(-13)+(-12)+...+12+13+14+15
Once we drop the restriction that the summands are positive integers,
it becomes really fascinating!
Very close, TC. You just need to differentiate between odd/even (as Dave points out) and add a condition that there are "enough" positive integers around the center.
For N = Sum = n * C, the number of distinct ways are:
N odd: number of odd factors f of N where C > f / 2 (C = N / f)
N even: same as above for odd factors PLUS number of even integers e where e < N, N / e = M.5, and C > e / 2 (C = M.5)
Yet another instance where the simplest concepts (symmetry & center) also seem the most fruitful.
A slip ...
Of course for N odd we also have N / 2 = M.5 = C and n is even.
Which makes me wonder: where there's one slip surely there can be another ...
Hi Marc,
My conjecture goes further that what you say. Irrespective of whether N is odd or even, the number of ways in which it can be expressed as a sum of consecutive positive integers is equal to the number of odd factors of N (You can include 1 as an odd factor, and trivially the number itself as the sum of 1 consecutive integers). For Even N, the intuition says that there must be more values, but many of these values give you negative starting points (-a) from which you can cull numbers from -a to a to get the kind of sequence you want. At the same time, some of the odd factors give you positive starting values, but some give negative ones, and these seem to cancel out to effectively give you only the number of odd factors. I have some kind of outline of a proof, but am not yet sure.
I have been able to numerically verify this up to N of 1 million. Assuming my program has no bugs, this seems to suggest that this is true.
TC
tc, marc--
I can't believe I'm actually going to attempt a proof of tc's excellent conjecture, but here goes. Because of notation and a desire to be precise, this will take up lots of space. Pls bear with me!
[Of course, I will need your expertise to correct typos and analyze logic or algebraic flaws!]
I will use Marc's approach of representing any sum of consecutive integers as (number of consecutive integers) x (the 'center' or median of the integers).
Symbolically, I will write S = NxM, where S is the number being represented as a sum, N is the number of terms and M is the median of the set. At this point, N must be an integer but M could be that decimal Marc referred to.
Since tc's conjecture is really an if and only if statement, I will need to demonstrate
(1) Every representation of S as a sum of consecutive integers corresponds to a UNIQUE odd factor of S and
(2) Every odd factor of S corresponds to a UNIQUE representation of S as a sum.
I will demonstrate the ideas first using numerical examples.
S = 10 = 1+2+3+4. I need to show that this representation corresponds to a unique odd factor of 10:
Using Marc's system, this representation corresponds to
4 x 2.5. No odd factors yet! But we can rewrite this as 2 x 5. Thus, if our sum consists of an even number of terms, 2y, with a median of
x + 0.5, then we can rewrite this as S = (y) (2x+1). 2x+1 therefore is the unique odd factor in this case.
S = 9 = 4+5 = 2 x 4.5 = 1 x 9; here 9 is that unique odd factor (remember in this case, the unique odd factor comes from doubling the decimal--I'm ignoring the other factor even it too is odd).
S = 12 = 3+4+5 = 3 x 4
Since 3 is already odd, we're done.
S = 15 = 1+2+3+4+5 = 5x3
Looks like we have a choice of odd factors here, but since I get to define the unique correspondence, I will choose 5, the number of terms. Since this number is unique for a given sum, we're ok.
S = 15 = 4+5+6 = 3x5.
Again we have a choice but as explained above, we will assign 3 to this sum since 3 is the number of terms.
S = 9 = 3+3+3 = 3x3.
Guess which odd number I will choose!
These examples demonstrate in general how we would assign a UNIQUE odd factor to EACH possible representation of S. I'll omit the details if you don't mind.
The other part of the biconditional appears to be much messier with many cases to consider, but I've reduced it to two, following tc's lead.
(2) I need to demonstrate that each odd factor of S corresponds to a UNIQUE representation of S as a sum. Again, I will start with examples and then move on to the algebraic rigor:
S = 24, 3 is an odd factor:
24 = 3x8 = 7+8+9. This representation of 24 as a sum of 3 consecutive positive integers whose median is 8 is unique.
Note: 24 has no other odd factors and this representation is the only one!
S = 15; 5 is an odd factor:
15 = 5x3 = 1+2+3+4+5. Thus 5 corresponds to the unique representation 15 as a sum of 5 consecutive positive integers.
S = 15; 3 is an odd factor;
15 = 3x5 = 4+5+6. Thus 3 corresponds to this unique representation.
Ok, now it gets interesting:
S = 21; 7 is an odd factor but
21 = 7x3 cannot be written as a sum of 7 consecutive positive integers whose 'center' is 3. What to do?
Write 21 = 7x3 = 6 x 3.5 which corresponds to the unique representation:
21 = 1+2+3+4+5+6, a sum of 6 terms whose center is 3.5. Algebraically, we will see that this rewrite is necessary because 7 is not less than or equal to 2x3-1. I'll clarify that later.
S=30, 15 is an odd factor. Certainly we are not going to represent 30 as a sum of 15 consecutive positive integers so we employ the same approach as before:
30 = 15 x 2 = 4 x 7.5, which corresponds to the unique representation:
30 = 6+7+8+9, 4 terms with a 'center' of 7.5.
What I found fascinating is that for each odd factor, N, there were really only TWO cases to consider.
I will use the following symbols:
S = NxM, where N is odd and M is an integer. It's irrelevant whether M is odd or even! Since N is odd, we can always write S as a sum of N consecutive integers with a median of M. The issue is to guarantee that these terms are all positive. In particular, the FIRST TERM has to be positive. The first term will always be given by M - (N-1)/2, when N is odd. One could derive this by using the formula for the sum of an arithmetic series or, better, realize that we can split S into 3 parts, the (N-1)/2 terms below M, the (N-1)/2 terms above M and M itself). Our first term is positive if
M - (N-1)/2 >= 1 which leads to
2M - N+1 >= 2 or N < = 2M - 1. We now have our two cases to complete the proof:
Case I: N < = 2M-1
This is the case we used above to derive the expression 2M-1. In this case, we can represent S uniquely as the sum of N consecutive positive integers with a 'center' of M.
Case II: N > 2M-1
(Think: 30 = 15x2 or 21 = 7x3]
In this case, we rewrite NxM as
2M x (N/2). Note that it is irrelevant whether M is odd or even as mentioned above. This leads to the representation of S as a sum of 2M consecutive integers with a median of N/2. But we must show that the first term is positive as before to produce the desired representation:
This time, the first term will be given by (N+1)/2 - M (details omitted) which I will now prove is > = to 1:
(N+1)/2 - M >= 1 iff
N+1 - 2M >= 2 iff
N >= 2M+1. But N is an odd integer and N > 2M-1, therefore the inequality follows.
Is anyone still conscious? If you are, let me know if this argument is sorta' kinda' valid. Of course, the kudos go to marc and tc who inspired me to devote an evening to this (now watch the logic fall apart!).
tc, your conjecture was wonderful and I believe middle school students might come up with something like this if given enough data to analyze. Marc, thank you for the symmetry approach. I believe there's a powerful idea there that students need to see.
Hi Dave,
Bravo! I think you have got it. The second part of the proof is quite cool. The first part is all there, though not with the same rigor as the second part, but the extension to rigor looks straightforward.
The way I was going about it was as follows: Consider a series beginning with a and k terms summing to N. Then
N = k(a+(k-1)/2). If k is odd, then both terms are integers. Also, if
a = N/k -(k-1)/2 >=1, we are fine. Otherwise, we consider (2N/k) instead of k. (Note that I said consider: this is a common trick of mathematicians in proofs without showing any of the thinking and possible angst that went into arriving at this step :-)). Then we can show that the series starts at (k+1)/2-N/k, which is positive. Thus, we have a valid series associated with every odd factor.
Now that the conjecture has been proven, it can be rightfully called the 'Totally Clueless Theorem' (TCT) :-)
This also leads us to the 'Totally Clueless Corollary (TCC)': The number of ways in which a number N can be expressed as the sum of consecutive integers is twice the number of odd factors of N.
TC
Hi Dave,
Bravo! I think you have got it. The second part of the proof is quite cool. The first part is all there, though not with the same rigor as the second part, but the extension to rigor looks straightforward.
The way I was going about it was as follows: Consider a series beginning with a and k terms summing to N. Then
N = k(a+(k-1)/2). If k is odd, then both terms are integers. Also, if
a = N/k -(k-1)/2 >=1, we are fine. Otherwise, we consider (2N/k) instead of k. (Note that I said consider: this is a common trick of mathematicians in proofs without showing any of the thinking and possible angst that went into arriving at this step :-)). Then we can show that the series starts at (k+1)/2-N/k, which is positive. Thus, we have a valid series associated with every odd factor.
Now that the conjecture has been proven, it can be rightfully called the 'Totally Clueless Theorem' (TCT) :-)
This also leads us to the 'Totally Clueless Corollary (TCC)': The number of ways in which a number N can be expressed as the sum of consecutive integers is twice the number of odd factors of N.
TC
Well done Dave and TC.
Interesting reasoning, and I like the TCT and the TCC. With these posts TC has now introduced, however, another paradox in mathematics - the TC Paradox:
totally clueless = not totally clueless
:)
Marc said:Which makes me wonder: where there's one slip surely there can be another ...
Marc, TC, Dave, you guys are just having some fun with each other, right? Because I'm not really following this. For any odd number N, we have:
N = ⌊N/2⌋ + ⌈N/2⌉
and that includes if N happens to be an odd prime. Also, considering the case of N=15, we have:
15 = 7 + 8
15 = 4 + 5 + 6
15 = 1 + 2 + 3 + 4 + 5
What am I missing here?
Hi Kurt,
I don't understand you question; or I don't see an issue.
According to the TCT, the number of ways is equal to the number of distinct odd factors. For 15, these are 1, 3, 5 and 15, and there are four ways to represent 15 as the sum of consecutive positive integers: the three you have shown plus the trivial one: 15.
Cheers,
TC
Okay, thanks TC. Somehow I wasn't counting both 1 and N as divisors. I'm going to have to go back and reread Dave's proof.
tc, kurt, marc--
It seems strange to be so engaged in math research mode but I guess that's what happens when one shares ideas in math!
TC, your theorem is publishable beyond this blog! You should get credit for it and Marc's acronyms for your conclusions may one day become as well known as _______?
Thank you for transforming a student activity into something far more significant. This is precisely what can happen when we turn our students on to math. When doors are opened, there will always be someone willing to take the risk to walk through and find a new 'dimension!'
Kurt, in my 'proof', I ignored the odd factor 1, since the original problem did require a sum of TWO or more consecutive positive integers. However, using the number itself, like 15, is critical to TC's conclusion.
Anyone feel I should submit this posting to the next Carnival of math over at jd2718?
Hi Dave,
Actually, I am quite comfortable with TCT and TCC.
You might also want to see
http://jd2718.wordpress.com/2007/01/30/puzzle-consecutive-integers-1-2/#comments
A similar discussion ensued there.
Cheers,
TC
It looks like the link got mangled in my previous post.
It is
http://jd2718.wordpress.com/2007/01/30/
puzzle-consecutive-integers-1-2/#comments
TC
"Anyone feel I should submit this posting to the next Carnival of math over at jd2718?"
YES!! I've enjoyed reading this thread, sorry I've been too busy to jump in. Again - yes, submit it!
I'll add a "me too" to the encouragement to submit this to the carnival. Of course you should mention that the comments are important, as usual.
When TC posted his conjecture, and his numerical verification, I thought, "surely one of us can prove that!" Glad you did, Dave!
Definitely you should submit this to the next carnival. (And I say that even though I'm displaying my ignorance in the comments, which seems to be a common occurrence for me lately.)
Kurt's first comment made me realize that indeed there was another slip :)
"N / 2 = M.5 = C and n is even"
was meant to be:
"N / n = M.5 = C and n is even"
Post a Comment