How to prove there are $\frac{3^n-1}{2}$ couples $A,B \in \mathcal{P}([n])$ such that $A \cup B = [n]$, $A \neq B$.

You seem to treat $A,B$ as unordered... that for instance $A=\{1,2\}$ and $B=\{3,4,5,6\}$ to be the same result than $A=\{3,4,5,6\}$ and $B=\{1,2\}$. For the time being let us go with the other interpretation that these are distinct outcomes as it makes the math far simpler.

Now... for each element $x$ in $[n]=\{1,2,3,\dots,n\}$ for it to be that $A\cup B=[n]$ as well as $A\subseteq [n]$ and $B\subseteq [n]$, exactly one of the following must be true:

• $x\in A$ and $x\notin B$
• $x\in B$ and $x\notin A$
• $x\in A$ and $x\in B$

For each element choose which of these three it is. Apply rule of product. That gives $3\times 3\times 3\times \cdots \times 3 = 3^n$ different choices of $A,B$.

This included in it however the possibility that we answered $x\in A$ and $x\in B$ for every $x$ which would have meant that $A=B$. You explicitly wanted to avoid this case, so subtracting $1$ will correct the count.

Finally, you seemed to be wanting to talk about unlabled pairs of sets rather than labeled pairs of sets. Dividing by $2$ corrects that aspect of the count. (Note that every outcome was counted twice. The only outcome that might have been counted only once was the case where $A=B$ but that was already removed)

This gives, as expected, the final result of:

$$\frac{3^n-1}{2}$$

Alternatively, using what you found in OEIS, take $\{A,B\}$ with $A\cap B=\emptyset,$ $A,B\neq \emptyset$ and consider $C=[n]\setminus (A\cup B)$ counted by the expression. Now, consider mapping that set to $\{A\cup C,B\cup C\},$ check that the properties that you required are satisfied and, moreover, this mapping is a bijection. So both problems have the same number of solutions.