Source: Ravi Subramanian
Step by step, for N=2,3,4,5....the corresponding probabilities p(2),p(3),p(4)...can be determined thanks to geometrical representations or by the integral calculus.They are respectively 1/2, 1/6, 1/24, 1/120...and the general term is 1/N!. For N=2,the two real numbers define the coordinates of a point M randomly located within a square of side 2. The points M such as the sum of the coordinates are lower than 2 are within a right isosceles triangle whose the hypotenuse is the diagonal of the square.So the required probability p(2) is defined by the ratio of the area of this right isosceles triangle to the area of the square,that is to say p(2)=1/2. The integral calculus leads to the same result, p(2) being defined by the integral 1/4*sum[x*dx] for x=0 to 2 For N=3,the three real numbers define a point M within a cube of side 3.The points M such as the sum of the coordinates are lower than 3 are within a pyramid whose 3 edges perpendicular to each other are 3 long.The required probability p(3) is defined by the ratio of the volume of this pyramid to the volume of the cube,that is to say p(3) = 1/6.Moreover,p(3) can be calculated by the integral 1/27*sum[x^2/2 * dx] for x=0 to 3 In order to calculate p(N) which corresponds to the general case,the integral calculus is the most adequate and it is easy to demonstrate that each of the coefficients of dx: x, x^2/2,x^3/6,x^4/24...for the different values of N=1,2,3,4...is the integral of the previous one.So p(N) = 1/N^N *sum[x^(N-1)/(N-1)! * dx] for x=0 to N.Therefore p(N) = 1/N!
Picking N real numbers at random in (0,N) is equivalent to picking a
point at random in an N-dimensional hypercube of side N. The probability
that their sum is less than N is the probability that the point also
lies in the N-dimensional right hyperpyramid within that cube that lies
between a given vertex and N-1 dimensional hyperplane which intersects
each of the vertices that share an edge with the given vertex. This
pyramid has 1/(N!) the volume of the cube, so the probability is 1/(N!).
Since not everybody can visualize such things, and some might not take the
formula for a the volume of a hyperpyramid for granted...
Let p(A,B,C) be the probability that the sum of a set of A numbers in the
range (0,B) is less than C.
Now, the Ath number varies from 0 to B, and for each value, we can compute
the probability that the remaining numbers sum to less than C minus that
number. So, p(A,B,C) is the integral over x=0..B of p(A-1,B,C-x)/B. Note,
though, that p(A,B,C) is zero if C<0, so we can reduce the integral to
that over x=0..C if C<=B.
Now, p(1,B,C) is the probability that a single number in (0,B) is less
than C; for 0<=C<=B, this is C/B.
What I want to show by induction is that p(A,B,C) for 0<=C<=B is
[(C/B)^A]/(A!), given p(A-1,B,C)=[(C/B)^(A-1)]/[(A-1)!] for 0<=C<=B.
We know p(A,B,C) = Integral[p(A-1,B,C-x)/B,x=0..C] for 0<=C<=B.
Substiting our given formula,
p(A,B,C) = Integral[([(C-x)/B]^[A-1])/(B*[(A-1)!]),x=0..C].
= 1/(B*[B^(A-1)]*[A-1]!) * Integral[(C-x)^(A-1),x=0..C]
Now, I can use the same symmetry/change of variables trick I used in
the last POTW problem to replace C-x in the integral with x, since
the integral is from 0 to C.
The Integral[x^(A-1),x=0..C] = (C^A)/A, so:
p(A,B,C) = [(C^A)/(B^A)]/([A-1]!*A) = [(C/B)^A]/(A!).
For our problem, A=B=C=N, and this reduces to 1/(N!).