Permutations With No Consecutive Numbers - Need Push In The Right Direction

[golmschenk]

First I'd like to mention I don't want the answer, I'd just like a hint in the direction which I should start working in. I just don't know how to begin the problem.

Homework Statement

How many permutations of 1, 2, . . . , n are there in which i is never immediately
followed by i + 1, i = 1, 2, . . . , n − 1? Show your answer is equal to D_{n} + D_{n-1}. (superscripts should be subscripts, I'm not sure why they aren't)

D_{n} being the number of derangements of a set with n elements.

Homework Equations

D_{n} = ^{n}_{k=0}\sum(-1)^{k}(\stackrel{n}{k})(n-k)!

(also, if someone wouldn't mind telling me how to get the conditions around the sigma for the sum correctly that would be great)

3. The Attempt at a Solution [/bn]

Again, it's the beginning I've been having problems with. I started counting cases, but that definitely seems like the long and difficult way of solving this. I've tried to simplify D_{n} + D_{n-1} to see if it might give me some hint into what I should be doing, but haven't gotten anything out of it. Any hints? Maybe all it will take would even just be a one word hint. I just need to get a push in the right direction. Thanks!

 

[jbunniii]

I'm not sure how to solve the problem (I'll certainly think about it), but I can give you a hand with the typesetting. You can click on each of the expressions below to see the TeX code that produced them.

D^{n-1}

D_{n-1}

\sum_{k=0}^{n} (-1)^k {n \choose k} (n - k)!