In our case, b = 3+ v 5 since b 1 = 1. It follows that b n > b and thus, b =
t hus

$$b_{1}\cdot\cdot\cdot b_{p}\geq\left({\frac{3+{\sqrt{5}}}{6}}\right)^{p}.$$

From (4.5), we know that the number of legal possible matches is greater than

$$3^{p}\left(\frac{3+\sqrt{5}}{6}\right)^{p}=\left(\frac{3+\sqrt{5}}{2}\right)^{p}.\tag{4.13}$$
$${\mathrm{is~in~}}\Theta\left(\left({\frac{3+{\sqrt{5}}}{2}}\right)^{p}\right),$$

To prove that the expected number of legal possible matches L 1 for M 1 is in O
bp - b. From (4.11) and (4.12), we have let ap = b

$$\alpha_{p}=b_{p}-\,b=\frac{b_{p-1}-\,b}{9b b_{p-1}}\leq d\alpha_{p-1}\,,\ \ 0<d<1\,,$$

which means that the series

$$(1+{\frac{\alpha_{1}}{b}})\cdot\cdot\cdot(1+{\frac{\alpha_{p}}{b}})$$

em is convergent. It follows that converges to a finite positive constant c . Therefo

$$b_{1}\cdot\cdot\cdot b_{p}=(\,b+\,\alpha_{1}\,)\cdots(\,b+\,\alpha_{p})\tag{4.14}$$ $$=b^{p}\left(1\,+\frac{\alpha_{1}}{b}\right)\cdot\cdot\cdot\left(1\,+\frac{\alpha_{p}}{b}\right)$$ $$\leq c\left(\frac{3\,+\,\sqrt{5}}{6}\right)^{p}$$

for sufficient large p and some constant c.

Similarly, we can show that the number of legal possible matches L 2 for M 2 is in
  
. Recalling that the number of legal possible matches L for the t-3-module satisfies L 1 L 2 ≤ L ≤ 27L 1 L 2 , the second conclusion follows.

□
The following Lemma calculates the probability that a matching local fitness function implies the matched 3-module.

Lemma 4.3. Given a 3-module x V y V w, x V y V w, and a local fitness function g such that the main variable xg of g is one of the three Boolean variables [x],[y],[w], let z =
2 + α, 0 ≤ α ≤ 1 be the parameter in the fixed ratio model N ( n, 2, z ). Then the probability that g contains the 3-module is

$$(4\,,15)$$
$$p_{0}\,=\,\left({\frac{1}{{\binom{n-1}{2}}}}\right)\,\left({\frac{1}{28}}(1\,-\,\alpha)\,+\,{\frac{6}{56}}\alpha\right)$$
