Very well done Guybrush Threepwood, it took you all of about one minute. (quicker than I could type my clarifying follow up post).
The problem from which the sequence was derived is as follows :
Consider the problem of matching up n items with their respective owners and doing it randomly. (Just like the recent problem posted here about a waiter handing the five different coats back to the five different patrons in the restaruant).
I was just trying to work out in how many ways you could get it totally wrong so that nobody at all got their correct item (and hence the probablity of getting every one wrong).
At first I had some trouble doing it analytically so I just manually enumerated the first few terms and tried to guess the sequence in the hope that it would inspire me to think of an analytic solution.
What is interesting is that I eventually got an analytically derived solution and it "looked" totally different to my guessed solution, yet did in fact yield an identical sequence when I calculated it.
Even more interesting is that your solution is different again (to both my solutions) yet also yeilds the same sequence. I'm sure it would be possible to prove that all three sequences are identical, though I haven't got time right now.
Here are the three sequences.
1. (Guessed by me) x_n = n \, x_{n-1} + 2\, {\rm even}(n) - 1
2. (solved by me) x_n = n! - 1 - \sum_{k=1}^{n-1} {\rm C}_k^n \,x_k
3. Guybrush Threepwood's solution. x_n = (n-1)\, (x_{n-1} + x_{n-2})
Note that even(n) is the function that is 1 if n is even and zero if n is odd.
As you can see my solution is pretty ugly, I like Guybrush's much better. Cool how they all give the same answer though. :)
PS. Note that I changed the "n" in Guybrush's formula to "n-1" simply to make it consistent with the index set of [1,2,3..] that I had used as opposed to [0,1,2..]
