Where "a form" for some RRE matrix is its description in terms of the number of all-zero rows it has and the position of pivots in the non-zero rows.
I've tried using induction, the base case is obvious enough:
$$ \left[ \begin{array}{c} 0 \end{array} \right], \left[ \begin{array}{c} 1 \end{array} \right] \rightarrow 2^1$$
After that, I assume that the total number of forms for the $n$ step is $2^n$, which has to be the sum of the different number of forms for each number $0 ,..., n$ of zero rows, the specifics of which I ignore for now (really, because I couldn't prove it myself).
Then, for each $n \times n$ form with given number of zero rows $Z$, I can embed it in a $(n+1) \times (n+1)$ matrix where the first zero row $z$ from the embedded matrix can be extended to have an $z_{n+1}$ entry in $\{1, 0\}$. If $z_{n+1} = 0$, there is a one-to-one correspondence with the sets of $n\times n$ forms indexed by $Z$, except when $Z=0$. The same argument applies to $z_{n+1} = 1$. Notice that for the $Z=0$ case, the smaller matrix can be embedded in a matrix where the last entry is either $0$ or $1$, which results in two RRE additional forms for the larger matrix.
Finally, the two one-to-one mappings contribute $2^n -1$ forms each. Adding the last two cases, we have $2^n - 1 + 2^n -1 +2 = 2^{n+1}$ forms and the induction is complete.
I feel my reasoning is somewhat convoluted, so I'd appreciate it if any flaws could be pointed out. My textbook had a hint about using Pascal's triangle, and I did notice that the number of forms linked to each $Z$ follows the pattern, but I was unable to set up a counting scheme for all possible pivot positions to show that this applies generally, so I would appreciate guidance in that regard.
