Problem source

A set of $2N+1$ rods consists of one of each length $1,2,\ldots,2N,2N+1$, where $N$ is an integer greater than 1. Three different rods are selected from the set. Suppose their lengths are $a,b$ and $c$, where $a > b > c$. Given that $a$ is even and fixed, show, by considering the possible values of $b$, that the number of selections in which a triangle can then be formed from the three rods is 
\[
1+3+5+\cdots+(a-3),
\]
where we allow only non-degenerate triangles (i.e. triangles with non-zero area). 
Similarly obtain the number of selections in which a triangle may be formed when $a$ takes some fixed odd value. Write down a formula for the number of ways of forming a non-degenerate triangle and verify it for $N=3$. 
Hence show that, if three rods are drawn at random without replacement, then the probability that they can form a non-degenerate triangle is 
\[
\frac{(N-1)(4N+1)}{2(4N^{2}-1)}.
\]

Solution source

Suppose we have $a = 2k$, it is necessary (by the triangle inequality) that $b + c > a$.

So the smallest $b$ can be is $k+1$, and then $c$ must be $k$ (1 choice).
Then $b$ could be $k+2$ and $c$ can be $k+1$, $k$, $k-1$ (3 choices).

Suppose $b = k+i$ then $c$ can be $k+i-1, \ldots, k-i+1$ which is $2i-1$ choices. 

This works until $b = 2k-1$ and there are $2(k-1)-1 = 2k-3 = a-3$ choices.

Therefore there are $1 + 3 + 5 + \cdots + (a-3)$ total choices.

If $a = 2k+1$ then, 

$b = k+1$ is not possible
$b = k+2$ we have $a = k+1, k$ (2 choices)
$b = k+3$ we have $a = k+2, k+1, k, k-1$ (4 choices)
$b = k + i$ we have $a = k+i-1, \cdots, k-i+2$ ($2i-2$ choices)

This works until $b = k+k$ with $2k-2 = a-3$ choices.
So $2 + 4 + \cdots + (a-3)$


If $a$ is even, we have $\left ( \frac{a-2}{2} \right)^2$
If $a$ is odd we have $\frac{(a-3)(a-1)}{4}$

Therefore the total number is:

\begin{align*}
C &= \sum_{k=2}^N \left ( \frac{(2k-2)^2}{4} + \frac{(2k+1-3)(2k+1-1)}{4} \right) \\
&= \sum_{k=2}^N \left ( (k-1)^2 + (k-1)k\right) \\
&= \sum_{k=2}^N (2k^2-3k+1) \\
&=  \sum_{k=1}^N (2k^2-3k+1) \\
&= \frac{N(N+1)(2N+1)}{3} - \frac{3N(N+1)}{2} + N \\
&= \frac{N((N+1)(4N+2-9)+6)}{6} \\
&= \frac{N(4N+1)(N-1)}{6} \\
\end{align*}

When $N = 3$ we have $1, 2, \cdots, 7$ sticks, and so

$a = 4$, $1$ option
$a = 5$, $2$ options
$a = 6$ $4$ options
$a = 7$ $6$ options

for a total of $13$. $\frac{3 \cdot 13 \cdot 2}{6} = 13$ so this is promising,

There are $\binom{2N+1}{3}$ ways to choose three sticks (in order) and of those our formula tells us how many are valid, therefore

\begin{align*}
&& P &= \frac{ \frac{N(4N+1)(N-1)}{6} }{\frac{(2N+1)2N(2N-1)}{6}} \\
&&&= \frac{(4N+1)(N-1)}{2(4N^2-1)}
\end{align*}