How many partitions are there for $\{1,\cdots,100\}$ for $3$ sets, $A,B,C$, such that $A$ cannot contain consecutive numbers ($\left|a-b\right|=1$)
Anyway, I thought about using recurrence relation here. Where $a_0 = 1$, $a_1 = 3$, but I'm not sure how to build the general case, $a_n$.
Let $a_n$ be the number of partitions of $\{1,2,...,n\}$ into $A,B,C$ where $n\in A$,
$b_n$ the number of partitions of $\{1,2,...,n\}$ where $n\in B$, and $c_n=b_n$.
Set up the recursions, for example $a_{n+1}=b_n+c_n$.