Cardinality of $\{:\{1, \ldots , \} → \{0,1,2\}\mid ∀ ∈ \{1, \ldots ,  − 1\}: () + ( + 1) ≠ 4\}$ 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?

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}$.

