I think you want to find the number of ordered pairs $(A,B)$ such that $A\subseteq S$ ($A$ is a subset of $S$), $B\subseteq S$, and $A\cap B\ne \emptyset$.
First we count the number of ordered pairs $(A,B)$ of subsets of $S$. There are $2^n$ choices for $A$, and for each such choice there are $2^n$ choices for $B$, for a total of $2^{2n}$, that is, $4^n$.
Now we count the bad ordered pairs, the ones where $A\cap B=\emptyset$.
To make such an ordered pair, for every $k\le n$ we have $3$ choices for what to do with $k$: (i) $k\in A$ and $k\not\in B$; (ii) $k\in B$ and $k\not\in A$; (iii) $k$ in neither $A$ nor $B$. So there are $3^n$ bad ordered pairs.
It follows that the required number of ordered pairs is $4^{n}-3^n$.
Remark: Your procedure is either correct or nearly correct. You also went after the "bad" pairs. Using the binomial theorem on your sum should give us $3^n$, or something close to that.
First, find the number of unordered subsets of $[n]$ with no difference of 1, of size $k$. The number of these is ${n - k + 1 \choose k}$. If we have a subset $a_1, a_2, \ldots, a_k$ of $[n]$ in increasing order, with none of the differences 1, then $a_1, a_2 - 1, a_3 - 2, \cdots, a_k - (k-1)$ is a subset of $[n-k+1]$ in increasing order, and this transformation can be reversed. For example, consider the subsets of $[7]$ of size 3 with no difference 1; these are
$$135, 136, 137, 146, 147, 157, 246, 247, 257, 357$$
(where I write $135$ for $\{1, 3, 5\}$ for conciseness). We can subtract 1 from the second element and 2 from the third element of each of these to get
$$123, 124, 125, 134, 135, 145, 234, 235, 245, 345$$
Both of these contain ${7 - 3 + 1 \choose 3} = 10$ elements.
Now, as you've already noticed, each unordered set of size $k$ gives rise to $k!$ ordered sets. For size $n$ we can have $k$ as large as $\lceil n/2 \rceil$. So we have
$$f(n) = \sum_{k=1}^{\lceil n/2 \rceil} {n-k+1 \choose k} k! = \sum_{k=1}^{\lceil n/2 \rceil} {(n-k+1)! \over (n-2k+1)!}$$
For numerical values, see https://oeis.org/A122852 (as has already been observed) and subtract one. For example,
\begin{align} f(7) &= \sum_{k=1}^4 {8-k \choose k} k! \\
&= {7 \choose 1} 1! + {6 \choose 2} 2! + {5 \choose 3} 3! + {4 \choose 4} 4! \\
&= 7 \times 1+ 15 \times 2 + 10 \times 6 + 1 \times 24 \\
&= 121 \end{align}
Best Answer
$x+y=0 \iff x=0;y=0$. It'll be easy to count them all including $(0,0)$ and then subtracting one.
For any integer $W$ lets define $Q_w$ and $R_W$ as the unique two integers so that $W = 3Q_2 + R_W$ and $0 \le R_W < 3$. (In other words $Q_W$ is the whole number quotient of dividing $W$ by $3$ and $R_W$ is the remainder.)
Now for any $k \le M$ we will have $k = 3Q_k + R_k$ and so for any $v = 3j + R_k$ we will have $|k -v| = |(3Q_k + R_k) -(3j +R_k)| = |3Q_k -3j| = 3\times |Q_k -j|$ (and it's easy see that if $R_v\ne R_k$ then $|k-v| = |(3Q_k +R_k)-(3Q_v +R_v)| =|3(Q_k-Q_v) +(R_k-R_v)|=3\times |Q_k-Q_v| \pm (R_k-R_v)$ is not divisible by $3$)
So for each $k \le M$ there was $R_k, 3+R_k, 6 + R_k,......, 3H+R_k$ where $3H+R_k$ is the largest number of that form $\le N$. Now that number is either $3Q_N + R_k$ if $3Q_N + R_k \le N = 3Q_N + R_n$ (that is if $R_k \le R_n$), of that number is $3(Q_N-1) + R_k$ if $3Q_N + R_k > N$ (that is if $R_k > R_n$)
So there are 2 cases:
If $R_M \le R_N$ then for every $w \le M$ (there are $M+1$ such numbers) then for ever $3k + R_w$ with $k \le Q_N$ (there are $Q_N + 1$ such numbers) we will have their differences divisible by $3$.
Thus there are $(M + 1)(Q_N + 1) = (M+1)(\lfloor \frac N 3\rfloor + 1) = M\lfloor \frac N 3\rfloor + M + \lfloor \frac N 3\rfloor + 1$. And if we remove $(0,0)$ there are $M\lfloor \frac N 3\rfloor + M + \lfloor \frac N 3\rfloor$
And case 2 is if $R_M > R_N$ but that means $R_N < R_M$ and we do the same thing but in terms of every $w \le R_N$.
We get there are $(N+1)(Q_M +1) -1 = N\lfloor \frac M 3\rfloor + N + \lfloor \frac M 3\rfloor$