# probability of sum of two integers less than an integer

Two integers [not necessarily distinct] are chosen from the set {1,2,3,...,n}. What is the probability that their sum is <=k?

My approach is as follows. Let a and b be two integers. First we calculate the probability of the sum of a+b being equal to x [1<=x<=n]. WLOG let a be chosen first. For b= x-a to be positive, we must have 1<=a < x. This gives (x-1) possible values for a out of total n possible values. Probability of valid selection of a= (x-1)/n. For each valid selection of a, we have one and only one possible value of b. Only 1 value of b is then valid out of total n possible values. Thus probability of valid selection of b= 1/n. Thus probability of (a+b= x) = (x-1)/n(n-1).

Now probability of (a+b<=k) = Probability of (a+b= 2) + probability of (a+b= 3) + ... + probability of (a+b= k) = {1+2+3+4+5+...+(k-1)}n(n-1) = k(k-1)/n(n-1).

Can anybody please check if my approach is correct here?

-
Is the answer reasonable? It says the probability the sum is $\le n$ is $1$. That is not so. –  André Nicolas Jun 3 '13 at 17:19
Can't the sum be more than $n$? –  Thomas Andrews Jun 3 '13 at 17:20
@Welcome: Welcome to MSE! It really helps readability to format questions using Mathjax (see FAQ). Regards –  Amzoti Jun 3 '13 at 17:24

Let's change the problem a little. Instead of drawing from the numbers $1$ to $n$, we draw from the numbers $0$ to $n-1$. We want to find the probability that the sum is $\le j$, where $j=k-2$. After we solve that problem, it will be easy to write down the answer of the original problem.

Draw the square grid of all points (dots) with coordinates $(x,y)$, where $x$ and $y$ are integers, and $0\le x\le n-1$, $0\le y\le n-1$.

Now imagine drawing the line $x+y=j$. Note that if $j=n-1$, we are drawing the main diagonal of the grid. If $j\gt n-1$, we have drawn a line above the main diagonal. If $j\lt n-1$, we have drawn a line below the main diagonal.

Deal first with the case $j\le n-1$. The points of the grid that are on or below the line $x+y=j$ form a triangular grid, which has a total of $1+2+\cdots +(j+1)$ points. This sum is $\dfrac{(j+1)(j+2)}{2}$. The grid has $n^2$ points, and therefore the probability that the sum is $\le j$ is $$\frac{(j+1)(j+2)}{2n^2}.$$

Now we deal with $m\lt j\le 2n-2$. In this case, the probability that the sum is $\le j$ is $1$ minus the probability that the sum is $\ge j+1$. By symmetry, this is the same as the probability that the sum is $\le (2n-2)-(j+1)$. Thus, by our previous work, the required probability is $$1-\frac{(2n-j-2)(2n-j-1)}{2n^2}.$$

Remark: Your basic approach was fine, at least up to the "middle." After the middle, think dice. There is symmetry between sum $\le k$ and sum $\ge 14-k$.

My switch to somewhat more geometric language is inessential, and was made mainly for rhetorical purposes.

-

Notice if $k\le 1$ the probability is $0$, and if $k\ge 2n$ the probability is $1$, so let's assume $2\le k\le 2n-1$. For some $i$ satisfying $2\le i\le 2n-1$, how many ways can we choose $2$ numbers to add up to $i$? If $i\le n+1$, there are $i-1$ ways. If $i\ge n+2$, there are $2n-i+1$ ways.

Now, suppose $k\le n+1$, so by summing we find:

$$\sum_{i=2}^{k}i-1=\frac{k(k-1)}{2}$$

If $k\ge n+2$, if we sum from $i=2$ to $i=n+1$ we get $\frac{(n+1)n}{2}$, and then from $n+1$ to $k$ we get:

$$\sum_{i=n+2}^k2n-i+1=\frac{1}{2}(3n-k)(k-n-1)$$

Adding the amount for $i\le n+1$ we get:

$$2kn-\frac{k^2}{2}+\frac{k}{2}-n^2-n$$

Since there are $n^2$ choices altogether, we arrive at the following probabilities:

$$\begin{cases}\frac{k(k-1)}{2n^2}&1\le k\le n+1\\\frac{4kn-k^2+k-2n^2-2n}{2n^2}&n+2\le k\le 2n\end{cases}$$

-

Let $s=a+b$

I will find $P(s=k)$.

Clearly for $k<0$ and for $k>2n$ then $P(s=k)=0$

The other cases are as follows.

Let $x$ be the total no. of pairs $a,b$

Case 1:$k\le n$

Total no. of ways of selecting $a,b$ as an ordered pair such that $s=k$ is $(k-1)$.

Now as according to the question there is no ordering so to remove this ordering we have to divide this by $2$ if $k$ is odd(Reason:as there are no case where $a=b$ so the no. of ways in which $a,b$ can occur as ordered tuple is twice their own number).If $k$ is even then we have to subtract $1$ from it then divide it by $2$ and then again add $1$ to it.

SO we have ,

$P(s=k)=\frac{k-1}{2x},\text{if k is odd}$

$P(s=k)=\frac{k}{2x},\text{if k is even}$

Case 2:$k>n$

Again we will take ordered $(a,b)$ at first.

In this case it is better to visualise the case using dots and bars.

There are $k$ dots.In between these $k$ dots we will put a bar and call the number of dots on left side of the bar as $a$ and the dots on the right side of the bar as $b$.

But there is a restriction that $a,b\le n$

We can easily handle this restriction by allowing to put the bar $k-n$ th dot and $n+1$ th dot.

So the number of places to put the dot equals $(n+1-k+n)=2n-k+1$

Now again if $2n-k+2$ is odd or $k$ is odd then we have to divide this by $2$ else we have to subtract $1$ and divide it by $2$ and then add $1$.

So we have,

$P(s=k)=\frac{2n-k+1}{2x},\text{if k is odd}$

$P(s=k)=\frac{2n-k+2}{2x},\text{if k is even}$

Now we will find $x$.

There are $n$ choices for each $a$ and $b$. So the no. of ordered pairs $(a,b)$ equals $n^2$

Now according to $n$ is even or odd we must have,

$x=n^2/2 \text{if n is even}$

$x=(n^2+1)/2 \text {if n is odd}$

-