Is there a rigorous proof of this combinatorial identity? 
Theorem: For any pair of positive integers $n$ and $k$, the number of $k$-tuples of positive integers whose sum is $n$ is equal to
  the number of $(k − 1)$-element subsets of a set with $n − 1$
  elements.

Does anyone know of a rigorous mathematical proof to this theorem? All the examples I have seen thus far just use the "stars and bars" explanation.
 A: Stars and bars will explain it, but suppose we go for an inductive proof. So let $S(n,k)$ mean that the number of solutions to
$$x_1+x_2+ \cdots +x_k=n \tag{1}$$ with positive $x_j$ (order mattering) is given by $\binom{n-1}{k-1}.$ A few base cases are easily established, so we turn to breaking up the solutions of (1) into (A) those in which $x_k=1$ and (B) those in which $x_k>1.$ On subtracting the final $1,$ the type (A) solutions become those of
$$x_1+x_2+ \cdots +x_{k-1}=n-1, \tag{2}$$
of which there are by induction $\binom{n-2}{k-2}$ solutions, while subtracting $1$ in case (B) leaves the last term still positive at $x_k-1$ since $x_k>1$ in case (B). That is, this case gives
$$x_1+x_2+ \cdots +(x_k-1)=n-1 \tag{1}$$
which using the inductive hypothesis again has $\binom{n-2}{k-1}$ solutions. Then adding these two binomials for the cases (A) and (B) it results in $\binom{n-1}{k-1}$ using the Pascal identity.
I don't know if this approach is really any more rigorous than stars and bars, but it does give another approach to the count, one relying heavily on already knowing what the formula should be.
