Timeline for Non-enumerative proof that there are many derangements?

5 events

when toggle format	what		by	license	comment
Jan 20, 2012 at 16:06	comment	added	Robert Israel		Actually this last bit of magic is not needed. From the fact that $\frac{D(n)}{P(n)} = \frac{D(n-2)+D(n-1)}{P(n-2)+P(n-1)}$ with the $D$'s and $P$'s positive we get that $f(n)$ is between $f(n-1)$ and $f(n-2)$, and then $f(2k) \ge f(2k+1) \ge f(2k-1)$.
Jan 20, 2012 at 8:31	comment	added	Robert Israel		Now $$ \frac{f(n) - f(n-1)}{f(n-1) - f(n-2)} = \frac{\frac{D(n-2)+D(n-1)}{P(n-2)+P(n-1)} - \frac{D(n-1)}{P(n-1)}}{\frac{D(n-1)}{P(n-1)} - \frac{D(n-2)}{P(n-2)}} = - \frac{P(n-2)}{P(n-1)+P(n-2)} = -\frac{1}{n}$$
Jan 20, 2012 at 8:26	comment	added	Robert Israel		To produce a derangement $X$ of $\{1 \ldots n\}$, first select $X(1)$ from $\{2 \ldots n\}$ ($n−1$ ways to do this), then either have $X(X(1))=1$ and make a derangement of the remaining $n−2$ items, or take a derangement $Y$ of $\{2 \ldots n\}$, and if $Y(k)=X(1)$ let $X(k)=1$ and $X(i)=Y(i)$ for $i \in \{2 \ldots n\} \backslash \{k\}$. Thus the number $D(n)$ of derangements of $n$ letters satisfies $D(n)=(n−1)(D(n−2)+D(n−1))$. The number $P(n) = n!$ of permutations of $n$ letters also satisfies $P(n)=(n−1)(P(n−2)+P(n−1))$...
Jan 19, 2012 at 19:43	comment	added	Igor Rivin		Why is the first sentence true?
Jan 19, 2012 at 19:25	history	answered	Robert Israel	CC BY-SA 3.0