Proving the recurrence relation of the rank polynomial (or Tutte's) on a matroid. I'm reading through chapter 15 on Algebraic Graph Theory by Godsil and Royle.
The $\mathit{rank \ polynomial}$ for a matroid $M$ is defined as
$$R_M(x,y)=\sum_{A \subseteq\Omega} x^{rk(\Omega)-rk(A)}y^{|A|-rk(A)}, $$
where $rk(X)$ is the the rank function of a subset $X$ of the ground set $\Omega$ of the matroid $M$.
A $\mathit{loop}$ is defined as an element $e$ of the ground set such that $rk(e)=0$ and a $\mathit{coloop}$ is defined as an element $f$ of the amtroid such that $f$ is a loop in the dual matroid $M^*$. The dual matroid $M^*$ is defined as the matroid with the same ground set as $M$ and with rank function
$$ rk^*(A)= |A| +rk(\Omega \setminus A) - rk(\Omega). $$
There follows this theorem which I'm trying to prove:
Let $M$ be a matroid on $\Omega$ and let $e \in \Omega$. Then:
$$ R_M(x,y) = (1+y)R_{M \setminus e}(x,y), \ \ \mathrm{if \ e \ is \ a \ loop;}$$
$$ R_M(x,y) = (1+x)R_{M / e}(x,y), \ \ \mathrm{if \ e \ is \ a \ coloop;}$$
$$ R_M(x,y) = R_{M \setminus e}(x,y) + R_{M / e}(x,y), \ \ \mathrm{otherwise.} $$
I'm okay with the first statement:
\begin{align} R_M(x,y) &= \sum_{A \subseteq\Omega \setminus e} x^{rk(\Omega \setminus e)-rk(A)}y^{|A|-rk(A)} + \sum_{A \subseteq\Omega \setminus e} x^{rk(\Omega \setminus e)-rk(A \cup e)}y^{|A \cup e|-rk(A \cup e)} \\
&= R_{M \setminus e} (x,y) + \sum_{A \subseteq\Omega \setminus e} x^{rk(\Omega \setminus e)-rk(A)}y^{|A|+1 -rk(A)} \\
&= R_{M \setminus e} (x,y) + yR_{M \setminus e} (x,y) \\
&= (1+y)R_{M \setminus e} (x,y).
\end{align}
by observing that since $e$ is a loop it will not contribute to the rank of any subset.
I don't see the second statement.
First, I'll restate the definition of a contraction. Let $M$ be a matroid with ground set $\Omega$ and let $T \subset \Omega$. Define $ \rho$ on $\Omega \setminus T$ as $\rho(A)=rk(A \cup T)- rk(T)$. Then $M/T$ is the matroid with rank function $\rho$ defined on $\Omega \setminus T$.
Since $e$ is a coloop:
$$\rho(A)=rk(A \cup e)- rk(e)=rk(A) +rk(e)- rk(e)=rk(A)$$
As well, for loops and coloops, $M/e = M \setminus e$, so
\begin{align} R_M(x,y) &= \sum_{A \subseteq\Omega \setminus e} x^{rk(\Omega \setminus e)-rk(A)}y^{|A|-rk(A)} + \sum_{A \subseteq\Omega \setminus e} x^{rk(\Omega \setminus e)-rk(A \cup e)}y^{|A \cup e|-rk(A \cup e)} \\
&= R_{M / e} (x,y) + \sum_{A \subseteq\Omega \setminus e} x^{rk(\Omega \setminus e)-rk(A \cup e)}y^{|A \cup e| -rk(A \cup e)} \\
&= R_{M / e} (x,y) +  \sum_{A \subseteq\Omega \setminus e} x^{rk(\Omega \setminus e)-rk(A) -1}y^{|A|+1 -rk(A) -1}\\
&= (1+x^{-1})R_{M /e} (x,y)  \\
&\neq (1+x)R_{M / e} (x,y).
\end{align}
I understand the third statement for a graph matroid but it's not clear to me why for a general matroid $R_{M/e}$ accounts for all subsets that contain e.
Also, I'd appreciate some feedback regarding the statement of the question. Was it too detailed?
 A: The trick to proving these results is to break up the defining sum of the Tutte polynomial into two sums: one over all sets that do not contain $e$ and the other for all sets that do.
$$R_{M}(x,y) =
 \sum_{e \notin A \subset \Omega}x^{r(\Omega) - r(A)}y^{|A|-r(A)}+
 \sum_{e \in A \subset \Omega}x^{r(\Omega) - r(A)}y^{|A|-r(A)}
 $$
When $e$ is a loop the rank function of $M-e$ is $r'(A) = r(A) = r(A \cup e)$. So
$$
x^{r(\Omega) - r(A)}y^{|A|-r(A)} =
 \begin{cases}
 x^{r'(\Omega-e) - r'(A)}y^{|A|-r'(A)} &\text{ if $e \notin A$} \\
 x^{r'(\Omega-e) - r'(A-e)}y^{|A-e|+1-r'(A)}&\text{ if $e \in A$}
 \end{cases}
$$
So we have
\begin{align}
R_{M}(x,y)
 &= \sum_{e \notin A \subset \Omega}x^{r(\Omega) - r(A)}y^{|A|-r(A)}+
 \sum_{e \in A \subset \Omega}x^{r(\Omega) - r(A)}y^{|A|-r(A)} \\
 &= \sum_{e \notin A \subset \Omega}x^{r'(\Omega-e) - r'(A)}y^{|A|-r'(A)}+
 \sum_{e \in A \subset \Omega}x^{r'(\Omega-e) - r'(A-e)}y^{|A-e|+1-r'(A)} \\
 &= R_{M-e}(x,y) + yR_{M-e}(x,y)
\end{align}
and the first result holds.
When $e$ is a coloop the rank function of $M/e$ is $r''(A) = r(A \cup e) - r(e) = r(A \cup e) - 1$. So
$$
x^{r(\Omega) - r(A)}y^{|A|-r(A)} =
 \begin{cases}
 x^{r''(\Omega-e) + 1 - r''(A)}y^{|A|-r''(A)} &\text{ if $e \notin A$} \\
 x^{r''(\Omega-e)- r''(A-e)}y^{|A-e|-r''(A)} &\text{ if $e \in A$}
 \end{cases}
$$
So we have
\begin{align}
R_{M}(x,y)
 &= \sum_{e \notin A \subset \Omega}x^{r(\Omega) - r(A)}y^{|A|-r(A)}+
 \sum_{e \in A \subset \Omega}x^{r(\Omega) - r(A)}y^{|A|-r(A)}\\
 &= \sum_{e \notin A \subset \Omega}x^{r''(\Omega-e) + 1 - r''(A)}y^{|A|-r''(A)}+
 \sum_{e \in A \subset \Omega}x^{r''(\Omega-e)- r''(A-e)}y^{|A-e|-r''(A)}\\
 &= xR_{M/e}(x,y) + R_{M/e}(x,y)
\end{align}
and the second result holds.
Finally when $e$ is neither a loop nor coloop we have
$$
x^{r(\Omega) - r(A)}y^{|A|-r(A)} =
 \begin{cases}
 x^{r'(\Omega-e) - r'(A)}y^{|A|-r'(A)} &\text{ if $e \notin A$} \\
 x^{r''(\Omega-e)- r''(A-e)}y^{|A-e|-r''(A-e)} &\text{ if $e \in A$}
 \end{cases}
$$
where $r', r''$ are the rank functions of $M-e$ and $M/e$ respectively.
So we have
\begin{align}
R_{M}(x,y)
 &= \sum_{e \notin A \subset \Omega}x^{r'(\Omega-e) - r'(A)}y^{|A|-r'(A)}+
 \sum_{e \in A \subset \Omega}x^{r''(\Omega-e)- r''(A-e)}y^{|A-e|-r''(A)}\\
 &= R_{M/e}(x,y) + R_{M/e}(x,y)
\end{align}
and the final result holds.
