In how many ways can string $S=123456$ be rearranged if at least one character needs to move more than one place from its original position?
For example, string $12534$ satisfies the condition because in the original string $12345$ the position of five is $5$ (using one-based index) while in $12534$ the position of five is $3$ and $5-3>1$.
I thought to find first the number of strings where numbers can be moved at most one position to the left or to the right. This is the recurrence I have: $$ a_n=a_{n-1}+a_{n-2} $$ Now there're $6!$ possible permutations of $S$ so the number of possible ways that at least one digit moves more than one place from its original position is $6!-a_6=720-13=707$.
I feel like I'm missing some inclusion/exclusion logic here.
As already discussed in the comments, your approach and your recurrence are correct and you don't need inclusion–exclusion here. In a string of length $n$ with no number moved by more than one position, the $n$ has to be either in position $n$ or in position $n-1$. In the former case, the remaining $n-1$ numbers can form any admissible string of length $n-1$. In the latter case, the only number that's allowed to move to position $n$ is $n-1$, so $n-1$ and $n$ swap places, and the remaining $n-2$ numbers can form any admissible string of length $n-2$. Thus $a_n=a_{n-1}+a_{n-2}$. Since $a_0=a_1=1$, this yields the Fibonacci numbers.