Background
In the question here: Generalizing Catalan numbers: number of ways where we cross the diagonal $k$ times., I asked for the number of ways to go from the bottom left to top-right of an $n\times n$ grid (taking right and up steps) such that you cross the main diagonal exactly $k$ times. I denoted these numbers $R_{k,n}$. I was already forming a vague outline for a solution based on joriki's answer to this question: Using the Catalan numbers, revolving around the observation that if we think of $k$ cut-off points (where the path switches from one side of the main diagonal to the other), the generating function of the resulting recurrence becomes that of the Catalan numbers raised to the power $k+1$. This is because we can think of these numbers as the convolution of $k+1$ Catalan paths. I finally got a handle on the way this approach was double and triple counting the paths and finally landed on the following recurrence (see my answer for details):
$$2C_{n}^{(k+1)} = \sum\limits_{j=0}^{k}{k+1 \choose j+1}R_{j,n} \tag{1}$$
Here, the generating function of $C_n^{(k)}={2n+k \choose n} \frac{k}{2n+k} $ is given by the summation in equation (5.70) here: Proof of identity about generalized binomial sequences..
However, @metamorphy managed to side-step this double and triple counting problem by not allowing for empty paths and came up with the following generating function:
$$\rho_k(z) =\sum\limits_{n=1}^\infty R_{k,n}z^n= 2\big(B_2(z)-1\big)^{k+1}\tag{2}$$
This allowed the closed-form to be calculated in one fell swoop using equation (5.70) here: Proof of identity about generalized binomial sequences. (you'll also find the definition of $B_2(z)$ there - it's the generating function of the Catalan numbers).
$$R_{k-1,n}=\frac{2k}{n}\binom{2n}{n-k}\tag{2.1}$$
The question
Naturally, I wondered if I could have come up with this closed form on my own with my approach. This is the question, if you're given equation (1) and no context on the interpretation of $R_{k,n}$, how do you tell that the $R_{k,n}$ have the generating function given by equation (2)? Or an alternate route to the closed form of $R_{k,n}$ per equation (2.1)?
My attempt
From equation (1), we get:
$$2 \sum\limits_{n=1}^\infty C_n^{(k+1)}z^n= \sum\limits_{j=0}^{k} \sum\limits_{n=1}^\infty {k+1 \choose j+1} R_{j,n}x^n$$
Using equation (5.70) here: Proof of identity about generalized binomial sequences. for the LHS and the definition of $\rho(z)$ in equation (2) we get:
$$2(B_2(z)^{k+1}-1)=\sum\limits_{j=0}^k {k+1 \choose j+1} \rho_j(z) \tag{3}$$
Now, if I calculate $\rho_0(z)$ and then $\rho_1(z)$ from it using (3) and then $\rho_2(z)$ using the first two, I can see the pattern. Then, I can prove it by induction. This is well and good, but it's only possible because I already knew the answer. Otherwise, I'd be stuck with equation (1) and use it to find $R_{k,n}$ using for-loops for god knows how long. This is the reason I ask this question. How could I have gone from equation (1) to the closed form without any insight or help?