You are here:

Advanced Math/Probability

Advertisement


Question
What is the probability of divisibility of sum of first n numbers by n?

Answer
First, there is a fundamental issue with how you are defining probability here -- if you mean "Picking an integer n at random, what is the probability that the sum of 1 through n is divisible by n?" then this is not a well-founded question. You cannot select (uniformly) at random from the set of integers because this set is infinite.

Because it is impossible to pick a "random integer" you have to redefine the question.

Instead, let's pick a number from {1,2,3,...,N}, where N is just some number, nothing special about N except that we've had to specify a finite N so that the set is finite.

This allows us to really pick at random because we pick each number with probability 1/N.

First, if we choose such n from this set, what is 1+2+3+...+n ?

This formula is well known, and such numbers are called triangular numbers.

t(n) = 1 + 2 + 3 + ... + n = n(n+1)/2

Now, to ask whether t(n) is divisible by n is the same as asking whether:

t(n)/n = n(n+1)/(2n) = (n+1)/2

is an integer. This is an integer if n is odd.

So of the numbers {1,2,3,...,N}, how many are odd?

pr( n | 1+2+3..+n ) = pr( t(n)/n is an integer ) = pr( n+1 is even ) = pr( n is odd )

Here "pr" means probability of an event, and "a|b" means "a divides b evenly."

Now, if N is even, then exactly half the numbers from 1 to N are odd. If N is odd, it's slightly biased, in other words:

pr( n | 1+2+3..+n ) = 1/2 if N is even
pr( n | 1+2+3..+n ) = (N+1)/(2N) if N is odd

Let's call this P(N), so that:

P(N) = 1/2 if N is even
P(N) = (N+1)/(2N) if N is odd

Now, at this point, it's safe to say "The answer we want is obviously 1/2" because half of the entire set of integers is odd. And that's true, but still we are required to phrase this with some probabilistic meaning we have to really say this:

Take a sequence of values of N, say N = a(k), what is the highest and lowest possible values for P(a(k)) as we run through the sequence a(k)?

These two quantities are called limit superior and limit inferior and they tell us something about the range of probabilities that we're looking for. If we really wanted to "choose an integer at random" the best we can do is to choose from 1,2,...,N and then take the limit as N goes to infinity.

Fortunately in this case, 1/2 is constant so the limit there is 1/2 for even N, otherwise the limit is of (N+1)/(2N) which is also 1/2.

Thus the total "probability" in the sense that the probability as N goes to infinity is 1/2.

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.