You are here:

- Home
- Science
- Mathematics
- Advanced Math
- Proof by Induction

Advertisement

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

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

1. You aren't using induction. In fact, this is

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

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

- Add to this Answer
- Ask a Question

Rating(1-10) | Knowledgeability = 10 | Clarity of Response = 10 | Politeness = 10 |

Comment | great tutor |

Advanced Math

Answers by Expert:

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.

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.