Probability $3$ integers $\le n$ are side lengths of triangle Here is a question from my probability textbook:

Three different persons have each to name an integer not greater than $n$. Find the chance that the integers named will be such that every two are together greater than the third.

Here's what I did. After computing the cases up to $n = 7$ (which I'm not typing out here due to being too lazy), I was able to observe that we have the recursion$$p_1 = 1, \quad p_n = {{(n-1)^3 p_{n-1} + {{3n(n-1)}\over2} + 1}\over{n^3}}$$However, I don't know how to solve it. Can anyone help me?
Edit: I bountied the question. I'd like to see a complete self-contained solution solving the recurrence I give without reference to external sources such as OEIS, Wikipedia, etc.
 A: Letting $w_n$ be the number of permitted configurations we get the recursion
$$
\begin{align}
w_n &= 1  + 3(n-1) + 3 \binom{n-1}{2} + w_{n-1}\\ \tag1
&=w_{n-1} + 1  + \frac{3}{2} n (n-1) 
\end{align}
$$
Explanation: in the first line of $(1)$, each term in the RHS  corresponds to the configurations that have $3,2,1,0$ values equal to $n$. The initial condition is $w_1=1$, or also $w_0=0$.
Noting that $p_n = w_n/n^3$, this concides with your recursion.
To solve this, one can postulate $w_n =  a_1 n + a_2 n^2 + a_3 n^3$, replace on $(1)$ and solve for $a_i$. (This also can be attacked via generating functions, see eg). Or, noticing that $w_n - w_{n-1}$ is the discrete analog of the derivative, we can integrate the other side:
$$w_n - w_{n-1} = g_n \implies \sum_{k=1}^n g_k + w_0 = w_n $$
Then $$\begin{align}
w_n &= \sum_{k=1}^n \left[1 + \frac{3}{2} k (k-1) \right] \\
 &= \sum_{k=1}^n 1 + 3 \sum_{k=2}^n \binom{k}{2} \\
 &= n + 3 \binom{n+1}{3}  {\hskip 1cm} \\
&= \frac12 n^3+\frac12 n
\end{align}
$$
where we've used the Hockey-stick identity.
See also OIES A006003 where many alternative interpretations and results about this sequence are given.
The desired probability is then
$$p_n = \frac{w_n}{n^3}=\frac12 + \frac{1}{2n^2}$$
A: Calling the chosen integers $a,b$ and $c$, the only way to fail to be a triangle is if $a≥b+c$, or $b≥a+c$, or $c≥a+b$. These three events have the same probability and are disjoint, so you can find $P(a≥b+c)$ and then multiply by $3$.
$P(a≥b+c)$ can be found by counting favorable cases with a summation. For each possible value of $a$, we must find the number of ways to choose positive integers $1\le b,c\le n$ for which $b+c\le a$. This is the same as counting triples of positive integers $(b,c,d)$ for which $b+c+d=a+1$. Using stars and bars, the number of solutions is $\binom{a}2$, so the total number of $(a,b,c)$ is
$$
\sum_{a=2}^n\binom{a}2=\binom{n+1}3
$$
which is a special case of the hockey-stick identity. Finally,
$$
P(\text{triangle ineq. holds})={1-3\cdot P(a\ge b+c)}=1-3\cdot \frac{\binom{n+1}3}{n^3}=\frac12+\frac{1}{2n^2}
$$
In this limit, this probability is $1/2$. In fact, if you let $a,b,c$ be continuously chosen uniformly over the range $[0,1]$, then the probability that none of the three is larger than the sum of the other two is exactly $1/2$. The same proof works as well, using an integral instead of a sum.
