Let be the number of partitions of into classes such that no 2 consecutive integers are in the same class.
We'll see that: holds.
Indeed, the first term corresponds to the number of cases in which lives alone in its own class, otherwise, if we have built a partition of into classes where no 2 integers in a same class are consecutive, the number may be placed in of them, since it can't go where is.
From there we get where are the Stirling numbers of the second kind (*)
Now we directly sum over k:
Thus: where (considering the initial values)
From there: and since
It follows: (in the same way we can get the Generating function for the Stirling numbers of the second kind)