How was this really handy bijection thought up of? Here's a proof from my combinatorics textbook.
Theorem 1.6.5. For any positive integer $k$,
$$(1-x)^{-k}=\sum_{n\geq 0}\binom{n+k-1}{k-1}x^n$$
Proof: Let $S_n$ be the set of all $k$-tuples $(a_1,\dots ,a_k)\in N^k_{\geq 0}$ with $a_1+\cdots +a_k=n$. We previously showed that
$$|S_n|=[x^n](1-x)^{-k}$$Let $T_n$ denote the set of all $(k-1)$-element subsets of ${1,2,\dots ,n+k-1}$, thus
$$|T_n|={n+k-1 \choose k-1}$$
We will establish a bijection between $T_n$ and $S_n$.
For $A=\{a_1,a_2,\dots ,a_{k-1}\}\in T_n$, with $a_1<a_2<\cdots<a_{k-1}$, we define $f(A)=\sigma$ where
$$\sigma=(a_1-1,a_2-a_1-1,\dots ,a_k-a_{k-1}-1,(n+k)-a_k-1)$$
(proof that it is bijection follows)
My question is, how in earth would somebody derive such a useful bijection. Just by staring at $\sigma$, where this came from is very opaque - leading to this theorem being really hard to proof without giving you the bijection to use.
 A: It’s easier to think about it the other way around. Assume that you’ve gathered enough numerical data (by brute force, if necessary) to suspect that $|S_n|$ is a binomial coefficient with lower number $k-1$. Then you want somehow to relate solutions to $x_1+\ldots+x_k=n$ in non-negative integers to $(k-1)$-element subsets of something. The key insight is that a solution to $x_1+\ldots+x_k=n$ in non-negative integers determines a non-decreasing sequence of partial sums, one of which is automatically known and can therefore be discarded without loss of information, leaving only $k-1$ integers. 
Suppose that $a_1+\ldots+a_k=n$, where each $a_i\in\Bbb N$. For $i=1,\dots,k$ let $s_i=a_1+\ldots+a_i$. Then $0\le s_1\le s_2\le\ldots\le s_k=n$. We know that $s_k=n$, so in order to reconstruct $a_1,\dots,a_k$, we need only the first $k-1$ partial sums, $s_1,\dots,s_{k-1}$. This sets up a nice correspondence between solutions to $x_1+\ldots+x_k=n$ in non-negative integers and $(k-1)$-term sequences non-decreasing sequences $\langle s_1,\dots,s_{k-1}\rangle$ of non-negative integers such that $s_{k-1}\le n$. 
This doesn’t quite give me $(k-1)$-element sets, since it’s entirely possible that $s_i=s_{i+1}$ for some $i$, but I can always simply add $1$ to the first term, $2$, to the second, and so on: let $t_i=s_i+i$ for $i=1,\dots,k-1$. Then $1\le t_1<t_2<\ldots<t_{k-1}\le n+k-1$, and $\{t_1,\dots,t_{k-1}\}$ is a genuine $(k-1)$-element subset of $\{1,\dots,n+k-1\}$. 
It’s not hard to see that if I start with any $(k-1)$-element subset of $\{1,\dots,n+k-1\}$ and list it in increasing order as $\{t_1,\dots,t_{k-1}\}$, I can reverse the process by setting $s_i=t_i-i$ for $i=1,\dots,k-1$ and $s_k=n$, and then letting $a_1=s_1$ and $a_i=s_i-s_{i-1}$ for $i=1,\dots,k$.
A: Think of writing out $a_1+\cdots+a_k=n$ where the numbers in the left hand side are written in unary notation, that is $a_i$ is represented by a sequence of $a_i$ vertical strokes (the sequence is empty if $a_i=0$). Then you've always got $n+k-1$ symbols in the left hand side ($n$ strokes and $k-1$ plus signs). So you could find all such expressions by each time writing down $n+k-1$ vertical strokes in a row, and choosing any subset of $k-1$ of them to which you add a horizontal stroke to form a "$+$".
(A variation of this argument is called "stars and bars". However I find that argument presented in its Wikipedia article rather roundabout when applied to the current situation, as it amounts to taking $n+k$ stars, choosing $k-1$ of the $n+k-1$ spaces between the stars to place a bar in, and then removing one star form each of the $k$ non-empty groups of stars formed. Also the article has the names $n$ and $k$ interchanged.)
This shows that $|S_n|=\binom{n+k-1}{k-1}$, but using unary notation seems terribly primitive, so we can deduce what the numbers $a_i$ would be if we crossed the strokes at positions $p_1<p_2<\cdots<p_{k-1}$ (starting with position$~1$). Clearly $a_1=p_1-1$ and $a_n=(n+k-1)-p_{k-1}$, while all intermediate numbers are given by $a_i=p_i-p_{i-1}-1$. This gives the bijection you described (although you called the $p_i$ by the same name $a_i$).
