I like to study combinatorics a bit as a hobby, and recently a question I found interesting was posed asking to derive a recurrence for the generating function $G_n(x)$, the ordinary generating function for perfect matchings on the set $[2n]=\{1,2,\dots,2n\}$, where the coefficient of $x^s$ is the number $s$ of short edges. A short edge is an edge with form $\{i,i+1\}$.
The recurrence was $ G_n(x)=(x+2n-2)G_{n-1}(x)+(1-x)\frac{d}{dx}G_{n-1}(x). $
Why does it hold?
I rearranged this as $ G_n(x)=xG_{n-1}(x)+(2n-2)G_{n-1}(x)+\frac{d}{dx}G_{n-1}(x)-x\frac{d}{dx}G_{n-1}(x). $ Looking at the individual coefficients of the summands, I see that:
The coefficient of $x^s$ in $G_n(x)$ is the number of perfect matchings on $[2n]$ with $s$ short edges.
The coefficient of $x^s$ in $xG_{n-1}(x)$ is the number of perfect matchings on $[2n-2]$ with $s-1$ short edges.
The coefficient of $x^s$ in $(2n-2)G_{n-1}(x)$ is $2n-2$ times the number of perfect matchings on $[2n-2]$ with $s$ short edges.
The coefficient of $x^s$ in $\frac{d}{dx}G_{n-1}(x)$ is $s+1$ times the number of perfect matchings on $[2n-2]$ with $s+1$ short edges.
The coefficient of $x^s$ in $x\frac{d}{dx}G_{n-1}(x)$ is $s$ times the number of perfect matchings on $[2n-2]$ with $s$ short edges.
Denoting these quantities as $A$, $B$, $C$, $D$, and $E$, respectively, it should be that $A=B+C+D-E$. Is there some clever way to show that the four possibilities in the RHS count all possibilities? I believe this would show that the identity is true. Thank you.
With Michael Lugo's suggestion, it's probably better to consider $A+E=B+C+D$. So I'm trying to determine why $ (2n,s)+s(2n-2,s)=(2n-2,s-1)+(2n-2)(2n-2,s)+(s+1)(2n-2,s+1) $ where $(x,y)$ represents the number of perfect matchings on $x$ points with $y$ short edges.