You are here:

Advanced Math/Proof by Induction

Advertisement


Question
Hi Clyde I have a discrete maths course coming up after finishing Differential Equations and I purchased the book for study prior to the course and am lost. This question is number 37 page 267 Discrete Maths with Applications by Epp.
Lemma:


On the Outside of the rim of a circular disk the integers from one to thirty are painted in random order. Prove there must be three successive integers whos sum is at least forty-five.
I have to prove this by induction.
Let P equal set of numbers from one to thirty randomized
Let Q equal the highest of the set
30,28,29=87
QED.

I just need to know where this went wrong if it did.

Thanks

Chris

Answer
The proof you've presented really doesn't make sense for two reasons:

1. You aren't using induction. In fact, this is not a statement that has any parameter "n" for which you could prove it

2. You haven't given a proof that there should be any three consecutive numbers totaling 45, unless 30, 29, and 28 are consecutive. The distribution is random -- you can't assume those three occur together.



Now, I will prove this without using induction. This is a very common problem that has a simple solution -- a solution that does not use induction. I've looked up the problem in the text by Epp. It does not specify that you should use induction (although it is in the section about induction). So you may be wrong when you say "[you] have to prove this by induction." In fact, this problem appears to be a non-induction question thrown in to help you with the following problem (number 38).

Consider the numbers 1 through 30 arranged in a circle. There are 30 possible triples, and you can sum them all. In other words, if they are arranged as follows:

a[1] = 27
a[2] = 13
a[3] = 11
a[4] = 2
a[5] = 30
a[6] = 1
...
a[29] = 21
a[30] = 7


Then at each position, you can form the sum s[i] = a[i] + a[i+1] + a[i+2], where if i=29 or 30, you wrap around the ordering. So, in this example:

s[1] = 51
a[2] = 26
a[3] = 43
a[4] = 33
...
a[29] = 55
a[30] = 47


Well, in this example already there are three that total greater than 45, so that's good.

To prove this, consider the sum of all s[i], that is:

S = s[1] + s[2] + s[3] + ... + s[29] + s[30]

Each of the terms a[1], a[2], ..., a[30] are counted three times, so you get:

S = 3 ( a[1] + a[2] + ... + a[30] )

Since the order doesn't matter, you get:

S = 3 ( 1 + 2 + ... + 30 ) = 1395

Now, this is important because the average of the s[i] is S/30 = 46.5

For that reason, if 46.5 is the average s[i], at least one s[i] should be at least 45 (in fact, one of the s[i] should be at least 47).

And that's it. No induction required.




You can use this methodology for any number. The idea is you have 1 through n arranged in a circle, and you want to ensure that k consecutive numbers add up to some total (call this M). The above is the case is n=30 and k=4, but for any n and k, you get:

a[1] through a[n] some permutation of 1 through n.

s[1] through s[n] defined as the sum s[i] = a[i] + a[i+1] + ... a[i+k]

S = k n (n+1) / 2

s[i] average = k (n+1) / 2

which means that there is some s[i] that is at least M = k(n+1)/2, rounded up.

This argument is much better than any inductive argument you could devise.






Now, if you feel bound to prove this by induction, you can. But you have to come up with some statement that you can apply induction to at all (that is, a statement with some "n" in it) to which you could apply induction. That's the reason I wanted to prove the above first -- so that you know where to find this statement.

What you want to show, presumably, is that if you arrange 1 through n in a circle, you get at least 3(n+1)/2 rounded down as a sum of 3 consecutive numbers. If you prove this for all n, then that includes n=30, which is the one you wanted.

For n=3, this is trivial, since 3(3+1)/2 = 6, which is the only sum you get (1+2+3). That is the base case.

Assuming it's true for some value n, consider the arrangement of 1 through n+1 around the table. You can remove n+1 from its position temporarily and consider whether you already have 3(n+2)/2 somewhere on the table. If not, some argument can tell you that adding n+1 to the arrangement must make this happen. To have 3(n+1)/2 but not 3(n+2)/2 means the numbers are very evenly distributed -- no matter where the n+1 goes, it will be enough (with two of its neighbors) to get you to 3(n+2)/2

You could also do induction on the parameter "k" (or a double-induction, possibly).

But, as I stated, induction is not the most direct way to prove this statement (even with parameters like "n" or "k") and the problem does not require induction, as stated, so I suggest you just prove it directly, as above.

Advanced Math

All Answers


Answers by Expert:


Ask Experts

Volunteer


Clyde Oliver

Expertise

I can answer all questions up to, and including, graduate level mathematics. I am more likely to prefer questions beyond the level of calculus. I can answer any questions, from basic elementary number theory like how to prove the first three digits of powers of 2 repeat (they do, with period 100, starting at 8), all the way to advanced mathematics like proving Egorov's theorem or finding phase transitions in random networks.

Experience

I am a PhD educated mathematician working in research at a major university.

Organizations
AMS

Publications
Various research journals of mathematics. Various talks & presentations (some short, some long), about either interesting classical material or about research work.

Education/Credentials
BA mathematics & physics, PhD mathematics from a top 20 US school.

Awards and Honors
Various honors related to grades, various fellowships & scholarships, awards for contributions to mathematics and education at my schools, etc.

Past/Present Clients
In the past, and as my career progresses, I have worked and continue to work as an educator and mentor to students of varying age levels, skill levels, and educational levels.

©2016 About.com. All rights reserved.