Cardinality of $\{:\{1, \ldots , \} → \{0,1,2\}\mid ∀ ∈ \{1, \ldots , − 1\}: () + ( + 1) ≠ 4\}$

Question

What is the cardinality of this set?

$$\{:\{1, … , \} → \{0,1,2\}\mid ∀ ∈ \{1, … , − 1\}: () + ( + 1) ≠ 4\}$$

On a logical level, I understand that it must be the set of all functions for which $f(i+1)\neq f(i) \neq 2$. But there's no formula for the function, so.. How can this be found?

Answer 1

Let $a_n$ be the number of such functions. We have two cases:

• If $f(1)\in\{0,1\}$ then there is $2\cdot a_{n-1}$ such functions.
• If $f(1)=2$ then there is $2\cdot a_{n-2}$ such functions. So, all together $$a_n = 2a_{n-1} + 2a_{n-2}$$ with $a_1 = 3$ and $a_2=8$. This means that $$a_n = a\Big({1+\sqrt{3}}\Big)^n+ b\Big(1-\sqrt{3}\Big)^n$$ for some $a,b$ which you can get from boundary terms. Actually it is $a ={3+2\sqrt{3}\over 6}$ and $b ={3-2\sqrt{3}\over 6}$.

Answer 2

Let $S_n$ be the set to be counted and $s_n=|S_n|$. Write $S_n=\{x0|x \in S_{n-1}\} \cup \{x1|x \in S_{n-1}\} \cup \{x2|x \in S_{n-1}\} \setminus T_n$, where $T_n=\{y22|y \in S_{n-2}\}=\{z022|z \in S_{n-3}\} \cup \{z122|z \in S_{n-3}\}$. This gives you a recurrence of $s_n$.