You are here:

- Home
- Science
- Mathematics
- Advanced Math
- Probability

Advertisement

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

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.

- Add to this Answer
- Ask a Question

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

Comment | Fine! In this case one has to take the limits. So it comes 1/2 as n goes infinite. |

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.