Let $g_{n}$ be the no. of derangements with $n$ elements and $f_{n}$ the no. of permutations with one fixed point. Show that $|g_{n}-f_{n}|=1$ This is a problem from Loren Larson's "Problem solving through problems", 2.5.13, page 78.
Let $S_{n}=${$1,2,...,n$}. A derangement of $S_{n}$ is a permutation with no fixed points. Let $g_{n}$ be the number of derangements, and $f_{n}$ the number of permutations of $S_{n}$ with exactly one fixed point. Show that $|f_{n}-g_{n}|=1$
I proved that $g_{n}=(n-1)(g_{n-1}+g_{n-2})$, and by analyzing the number of permutations for $S_{3}$ and $S_{4}$ I've conjectured that $g_{2n}=f_{2n}+1$, and $g_{2n+1}=f_{2n+1}-1$, although I don't know how to prove it. I also found that $f_{n+1}=(n+1)g_{n}$.
 A: HINT: Let $\pi$ be a permutation of $S_n$ with exactly one fixed point. Let $k$ be the fixed point; then $\pi\upharpoonright(S_n\setminus\{k\})$ is a derangement of $S_n\setminus\{k\}$. Let 
$$s:S_n\setminus\{k\}\to S_{n-1}:\ell\mapsto\begin{cases}
\ell,&\text{if }\ell<k\\
\ell-1,&\text{if }\ell>k\;;
\end{cases}\tag{1}$$
$s$ is a bijection, and $s\circ\big(\pi\upharpoonright(S_n\setminus\{k\})\big)\circ s^{-1}$ is a derangement of $S_{n-1}$. Conversely, if $\pi$ is a derangement of $S_{n-1}$, $k\in S_n$, and $s$ is defined by $(1)$, then $s^{-1}\circ\pi\circ s$ is a permutation of $S_n$ having exactly one fixed point, $k$. Thus, $f_n=ng_{n-1}$. If you combine this with your recurrence for $g_n$, you should be able to finish the proof (and incidentally prove your observation about odd/even subscripts), but feel free to leave a question if you get stuck.
A: Let $D_n$ be the number of derangements in $S_n$. Obviously the number of permutations with exactly one fixed point is given by $n D_{n-1}$, so we just have to prove that for every $n$,
$$ A_n = D_n-nD_{n-1}\in\{-1,1\}.$$
Let $\sigma$ be a derangement in $S_n$ and let $m=\sigma^{-1}(n)$. If we consider:
$$ \tau = \sigma\, (n m) $$
i.e. the permutation we get by swapping the images of $n$ and $m$, we obviously have $\tau(n)=n$. Then, there are two cases: if $\tau(m)=m$, $\tau$ has exactly two fixed points, otherwise $n$ is the only fixed point. That leads (see also this question) to:
$$ D_n = (n-1)\left(D_{n-1}+D_{n-2}\right) $$
that can be written as $A_n = -A_{n-1}$. Since $A_2=1$, the claim follows by induction.
A: The generating function of derangements is
$$\exp(-z) \frac{1}{1-z}.$$
This is because the species here is
$$\mathfrak{P}(\mathfrak{C}_{=2}(\mathcal{Z})
+ \mathfrak{C}_{=3}(\mathcal{Z})
+ \mathfrak{C}_{=4}(\mathcal{Z})
+ \cdots)$$
which gives
$$\exp\left(\frac{z^2}{2}+\frac{z^3}{3}
+\frac{z^4}{4}+\cdots\right).$$
Hence we have for the number of derangements
$$n! [z^n] \exp(-z) \frac{1}{1-z}$$
The generating function of permutations with fixed points marked is
$$\exp\left(uz - z +\log\frac{1}{1-z}\right)$$
which is
$$\exp(uz-z)\frac{1}{1-z}$$
This is because the species here is
$$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{=1}(\mathcal{Z}) +
\mathfrak{C}_{=2}(\mathcal{Z})
+ \mathfrak{C}_{=3}(\mathcal{Z})
+ \mathfrak{C}_{=4}(\mathcal{Z})
+ \cdots)$$
which gives
$$\exp\left(uz + \frac{z^2}{2}+\frac{z^3}{3}
+\frac{z^4}{4}+\cdots\right).$$
Hence we have for the number of permutations with one fixed point
$$n! [z^n] [u] \exp(uz-z)\frac{1}{1-z}$$
which is 
$$n! [z^n] z \exp(-z)\frac{1}{1-z}.$$
The difference is
$$n! [z^n] (1-z) \exp(-z) \frac{1}{1-z}
= n! [z^n] \exp(-z) = (-1)^n,$$
thus proving the claim.
