Showing that $Q_n=D_n+D_{n-1}$ Let $T_n$ be the set of permutations of $\{1,2,\ldots,n\}$ which do not have $i$ immediately followed by $i+1$ for $1\le i\le n-1$; in other words, let
\begin{align}
T_n=\{\sigma \in S_n: \sigma(i)+1\ne\sigma(i+1) \text{ for all } 1\le i\le n-1\} .
\end{align}
Let $Q_n$ be the number of elements of $T_n$.  
Let $D_n$ be the number of derangements of $\{1,2,\ldots,n\}$.
It is not hard to show algebraically that $Q_n=D_n+D_{n-1}$, but I am having difficulty coming up with a combinatorial argument to show why this is true.  (I believe there are
$D_{n-1}$ elements of $T_n$ that leave $n$ fixed, and $D_n$ elements of $T_n$ that move $n$, but I don't know how to justify this combinatorially.)
 A: (Note: this answer does not contain a bijection between the two sets, which is what the OP was originally hoping for, but it does show that the two counting problems are structurally equivalent and therefore have the same answer.)
The belief stated in the last paragraph of your question is correct: we can show that the set $\mathcal{D}_{n-1}$ of derangements of $\{1,2,3,\ldots,n-1\}$ and the set of permutations $\sigma$ of $\{1,2,3,\ldots,n\}$ with the properties


*

*$\sigma(n)=n$,

*$\sigma(i+1)\ne\sigma(i)+1,$ for $1\le i\le n-1,$


are equinumerous.  That is, $\mathcal{D}_{n-1}$ and the set of elements of $T_n$ that fix $n$ have the same size.  Call the latter set $\overline{T}_n.$
This result will prove the equation in your title since there is an obvious bijection between the set of elements of $T_n$ that do not fix $n$ and the set $\overline{T}_{n+1}$ of elements of $T_{n+1}$ that do fix $n+1,$ which will then be equinumerous with $\mathcal{D}_n.$
To enumerate $\mathcal{D}_{n-1}$, let $F=S_{n-1}$ be the set of permutations of $1,2,\ldots,n-1.$  Let $F_j$ be the set of elements of $F$ that fix $j,$ that is, elements $\sigma$ such that $\sigma(j)=j.$  In general, let $F_{ijk\ldots}=F_i\cap F_j\cap F_k\cap\ldots$ be the set of elements that fix $i,$ $j,$ $k,\ldots$, that is, elements $\sigma$ such that $\sigma(i)=i,$ $\sigma(j)=j,$ $\sigma(k)=k,\ldots$  Observe that $\lvert F_{i_1i_2\ldots i_k}\rvert=(n-1-k)!$ since only $n-1-k$ elements are free to move.  Since the derangements are those elements that fix no element, the principle of inclusion-exclusion gives
$$\begin{aligned}\lvert\mathcal{D}_{n-1}\rvert&=\lvert F\rvert-\sum_{i=1}^{n-1}\lvert F_i\rvert+\sum_{1\le i<j\le n-1}\lvert F_{ij}\rvert-\ldots\\
&=(n-1)!-\binom{n-1}{1}(n-2)!+\binom{n-1}{2}(n-3)!-\ldots\end{aligned}$$
To enumerate $\overline{T}_n$, let $G$ be the set of permutations of $1,2,\ldots,n$ that fix $n.$  Let $G_i,$ $1\le i\le n-1,$ be the subset of $G$ consisting of elements $\sigma$ such that $\sigma(i+1)=\sigma(i)+1.$  In general, let $G_{ijk\ldots}=G_i\cap G_j\cap G_k\cap\ldots$ be the set of elements of $G$ such that $\sigma(i+1)=\sigma(i)+1,$ $\sigma(j+1)=\sigma(j)+1,$ $\sigma(k+1)=\sigma(k)+1,\ldots$  We claim that, once again, $\lvert G_{i_1i_2\ldots i_k}\rvert=(n-1-k)!.$  This follows by noting that every constraint $\sigma(i_j+1)=\sigma(i_j)+1$ reduces the number of elements that can move independently by $1,$ leaving only $n-1-k$ elements that are free to move.  One can imagine element $i$ becoming "glued" to element $i+1,$ so that they must move as a block.
For example, let $n=9$ and consider $G_{12478}.$  Since $8$ must immediately precede $9,$ which is fixed, and $7$ must immediately precede $8,$ which is now fixed as well, the elements $789$ are fixed.  At the same time, $2$ must immediately precede $3$ and $1$ must immediately precede $2,$ meaning that the string $123$ can only move as a block.  Similarly, the string $45$ can only move as a block.  As a consequence the number of permutations in $G_{12478}$ is the number of ways of permuting the "objects" $123,$ $45,$ and $6,$ with the object $789$ fixed in place.  So $G_{12478}=3!=(9-1-5)!,$ in agreement with the claim.
Since $\lvert G_{ijk\ldots}\rvert=\lvert F_{ijk\ldots}\rvert$ for all choices of subscripts, the principle of inclusion-exclusion implies that the computation of $\lvert\overline{T}_n\rvert$ is identical to that of $\lvert\mathcal{D}_{n-1}\rvert,$ so that they have the same final value:
$$\begin{aligned}\lvert\overline{T}_n\rvert&=\lvert G\rvert-\sum_{i=1}^{n-1}\lvert G_i\rvert+\sum_{1\le i<j\le n-1}\lvert G_{ij}\rvert-\ldots\\
&=(n-1)!-\binom{n-1}{1}(n-2)!+\binom{n-1}{2}(n-3)!-\ldots\end{aligned}$$
A: Here is another bijective proof of $Q_n=D_n+D_{n-1}$.
Define a succession of $\pi$ to be an instance of the subsequence $(i,i+1)$ occurring consecutively in $\pi$, so $Q_n$ is the number of permutations with zero successions. Define an extended succession of a $\pi$ to be either a succession, or the element $1$ occurring at the beginning of $\pi$. That is, the number of extended successions is equal to the number of successions when $\pi(1)\neq 1$, and is equal to one plus the number of successions when $\pi(1)=1$.
Using the bijection here, we can see that for any $k\in \{0,\dots,n\}$, the number of permutations of $\{1,\dots,n\}$ with exactly $k$ extended successions is equal to the number of permutations of $\{1,\dots,n\}$ with exactly $k$ fixed points.
Therefore, the equation $Q_n=D_n+D_{n-1}$ follows by breaking up all permutations $\pi \in Q_n$ according to whether $\pi(1)=1$.

*

*The number of $\pi$ with no successions for which $\pi(1)\neq 1$ is equal to the number of $\pi$ with zero extended successions, which by the linked bijection is equal to $D_n$.


*The number of $\pi$ with no successions for which $\pi(1)= 1$ is equal to the number of permutations of $\{2,\dots,n\}$ with zero successions and where $\pi(2)\neq 2$, which equals the number of permutations of $\{1,\dots,n-1\}$ with zero extended successions, which by the linked bijection equals $D_{n-1}$.
A: Let $\sigma$ be the circular permutation $i\mapsto i+1$.
Then, you can establish a bijection $D_n\cup D_{n-1}\to T_n$ (I abuse notation for $D_n$ to design the set as well as the cardinal) by mapping any $\tau$ to $\tau\circ\sigma$,where elements of $D_{n-1}$ are naturally extended with $n\mapsto n$. It is straightforward to verify that this is a bijection.
A: EDIT: What's below is actually WRONG, due to multiple issues noted in the comments (the equation taken modulo $n$ leads to situations where a consecutive $n1$ causes problems, and it's not necessarily a bijection.

I think a variant on dkuper's argument can be made to work.  
If I understand correctly, the permutations in $Q_n$ are those which satisfy $\sigma(i)+1 \neq \sigma(i+1)$ for $1 \leq i \leq n-1$.  Conversely, we can think of $D_n+D_{n-1}$ as consisting of those permutations satisfying $\tau(i) \neq i$ for $1 \leq i \leq n-1$ ($D_n$ corresponds to those permutations with $\tau(n) \neq n$ as well, while $D_{n-1}$ corresponds to fixing $\tau(n)=n$).  
This suggests that we construct our bijection in such a way that $\sigma(i)+1=\sigma(i+1)$ if and only if $\tau(i)=i$.  The former equation can be rewritten as $i=\sigma^{-1} (\sigma(i+1)-1)$.  So if we define our bijection by taking $\sigma$ to the permutation satisfying 
$$\tau(i)=\sigma^{-1}\left(\sigma(i+1)-1\right),$$
where addition and subtraction are taken modulo $n$, things work the way we want them to.
