Exercise 4.4.15* (Some combinatorics)

Question

Let $f(n)$ denote the number of sequences $a_1,a_2,\ldots,a_n$ that can be constructed where each $a_j$ is $+1, -1$, or $0$, subject to the restrictions that no consecutive terms can be $+1$, and no consecutive terms can be $-1$. Prove that $f(n)$ is the integer nearest to $\frac{1}{2}(1 + \sqrt{2})^{n+1}$.

Richard Ganaye · Accepted Answer

ewcommand{\N}{\mathbb{N}}

\begin{proof} Consider the set $A_n$ of  sequences $(a_1,a_2,\ldots,a_n) \in \{0, 1, -1 \}^n$ satisfying the restrictions that no consecutive terms can be $+1$, and no consecutive terms can be $-1$.
We define
\begin{align*}
U_n &= \{(a_1,a_2,\ldots,a_n) \in A_n \mid a_n = 0\},\
V_n &= \{(a_1,a_2,\ldots,a_n) \in A_n \mid a_n = 1\},\
W_n &= \{(a_1,a_2,\ldots,a_n) \in A_n \mid a_n = -1\},
\end{align*}
and $u_n = |U_n|, v_n = |V_n|, w_n = |W_n|$ the cardinalities of $U_n,\ V_n, \ W_n$.

Since $A_n$ is the disjoint union of $U_n, V_n, W_n$,
\begin{align}
f(n) = u_n + v_n + w_n.
\end{align}

Moreover, for $n \geq 2$, if we fix $a_n = 0$, then any sequence can precede $0$, so $u_n = u_{n-1} + v_{n-1} + w_{n-1}$. If we fix $a_n = 1$, only the sequences such that $a_{n-1} = 0$ or $-1$ are possible so that $v_n = u_{n-1} + w_{n-1}$, and similarly $w_n = u_{n-1} + v_{n-1}$. For $n\geq 2$, this gives the system
\begin{align}
&\left\{
\begin{array}{llll}
u_n &= u_{n-1} &+\,  v_{n-1} &+\,  w_{n-1}\
v_n &= u_{n-1} && +\,  w_{n-1}\
w_n &= u_{n-1} & +\, v_{n-1} &
\end{array}
ight.
\qquad
\left\{
\begin{array}{l}
u_1 =1\
v_1 = 1\
w_1 = 1.
\end{array}
ight.
\end{align}
Note that $v_1 = w_1$ and by (1), if $v_{n-1} = w_{n-1}$, then $v_n = w_n$, so 
$$\forall n \geq 1,\ v_n = w_n.$$
By eliminating $w_n$ we obtain for $n \geq 2$ the shortest system
\begin{align}
\left\{
\begin{array}{ll}
u_n &= u_{n-1} + 2 v_{n-1}\
v_n &= u_{n-1} + v_{n-1}
\end{array}
ight.
\qquad 
\left\{
\begin{array}{ll}
u_1 &= 1\
v_1 &= 1.
\end{array}
ight.
\end{align}
We give to $u_0$ and $u_1$ the conventional values $u_0 = 1, v_0 = 0$, so that for all $n \geq 1$,
\begin{align}
\left\{
\begin{array}{ll}
u_n &= u_{n-1} + 2 v_{n-1}\
v_n &= u_{n-1} +\  v_{n-1}
\end{array}
ight.
\qquad 
\left\{
\begin{array}{ll}
u_0 &= 1\
v_0 &= 0.
\end{array}
ight.
\end{align}
We may write (4) in the form
\begin{align}
&\begin{pmatrix}  u_n\ v_n \end{pmatrix} = 
\begin{pmatrix}  1 & 2 \ 1 & 1 \end{pmatrix} 
\begin{pmatrix}  u_{n-1}\ v_{n-1} \end{pmatrix}
 &(n\geq 1).
\end{align}
We define $A = \begin{pmatrix}  1 & 2 \ 1 & 1 \end{pmatrix}$, and $M_n =\begin{pmatrix}  u_n\ v_n \end{pmatrix}$, so that $M_{n+1} = A M_n$ for every $n \in \N$. Then
\begin{align*}
M_n = A^n M_0.
\end{align*}
The eigenvalues of $A$ are the roots of 
\begin{align*}
P_A(x) &= \det(A - \lambda I)\
&= \begin{vmatrix} 1 - x & 2\ 1 & 1 -x \end{vmatrix}\
&= (x-1)^2 - 2\
&= (x - 1 + \sqrt{2}) (x - 1 - \sqrt{2})\
&= (x - \lambda)(x - \mu),
\end{align*}
where 
$$\lambda = 1 + \sqrt{2}, \qquad \mu = 1 - \sqrt{2}.$$
The eigenvalues are distinct, so there is a matrix $P$ such that $P^{-1} A P = \begin{pmatrix}  \lambda & 0\ 0 & \mu \end{pmatrix}$. Therefore
$$A^n = P  \begin{pmatrix}  \lambda^n & 0\ 0 & \mu^n \end{pmatrix} P^{-1},$$
so
\begin{align*}
\begin{pmatrix}  u_n\ v_n \end{pmatrix} &= P  \begin{pmatrix}  \lambda^n & 0\ 0 & \mu^n \end{pmatrix} P^{-1} \begin{pmatrix}  u_0\ v_0 \end{pmatrix} \
&= \begin{pmatrix}  c \lambda^n + d \mu^n\ e \lambda^n + f \mu^n\end{pmatrix},
\end{align*}
where $c,d,e,f$ are constant real numbers.
Then 
\begin{align}
f(n) &= u_n + 2 v_n = a \lambda^n + b \mu ^n,
\end{align}
where $a = c + 2e,\ b = d + 2f$.

(Alternatively, we can prove (6) without linear algebra by showing with (4) that $u_{n+1} = 2u_n + u_{n-1},\ v_{n+1} = 2 v_n + v_{n-1}$ and  $f(n+1) = 2 f(n) + f(n-1)$ for $n \geq 1$, and using Theorem 4.10.)

We find $a$ and $b$ with the values $f(0) = u_0 + 2 v_0 = 1$ and $f(1) = u_1 + v_1 = 3$. Then
$$
\left\{
\begin{array}{lll}
a &+\ b &= 3,\
a\lambda &+\  b \mu &= 7,
\end{array}
ight.
$$
so
\begin{align*}
a= \frac{3- \mu}{\lambda - \mu} = \frac{2+\sqrt{2}}{2\sqrt{2}}= \frac{1}{2} (1 + \sqrt{2} ) =\frac{ \lambda}{2},\
b= \frac{\lambda - 3}{\lambda - \mu} = \frac{-2+\sqrt{2}}{2\sqrt{2}}= \frac{1}{2} (1 -\sqrt{2} ) =\frac{ \mu}{2}.
\end{align*}
Therefore
\begin{align*}
f(n) &= \frac{1}{2} (\lambda^{n+1} + \mu^{n+1}\
&=\frac{1}{2} \left[(1 + \sqrt{2})^{n+1} + (1 - \sqrt{2})^{n+1}ight].
\end{align*}
Moreover, $-1/2 < - \sqrt{2} < 0$, so $|1 - \sqrt{2}| < 1/2$, therefore
$$\frac{1}{2} \left| 1 - \sqrt{2} ight|^{n+1} <  \frac{1}{2^{n+2}} < \frac{1}{2},$$
thus
$$\left| f(n) - \frac{1}{2} \left[(1 + \sqrt{2})^{n+1} ight] ight|< \frac{1}{2}.$$
Therefore $f(n)$ is the integer nearest to $\frac{1}{2}(1 + \sqrt{2})^{n+1}$. We can write
$$f(n) = \left \lfloor \frac{1}{2}(1 + \sqrt{2})^{n+1} + \frac{1}{2} ight floor.$$
\end{proof}
Note: We give some ways to compute $f(n)$ with Sagemath.

\begin{verbatim}
def f(n):
    u, v = 1, 1
    for i in range(1, n):
        u, v = u + 2 * v, u + v
    return u + 2 * v
    
def f(n):
    a = (1/2) * (1 + sqrt(2))^(n + 1) + (1/2) * (1 - sqrt(2))^(n + 1)
    return int(round(a.n(), 2))
            
def f(n):
    a = (1/2) * (1 + sqrt(2))^(n + 1)
    return floor(a.n() + 0.5)
     
 def f(n):
     A =  matrix([[1,2], [1,1]])
     B = A^n
     return B[0][0]  + 2 * B[1][0]
     
  [f(n) for n in range(1, 10)]
           [3, 7, 17, 41, 99, 239, 577, 1393, 3363]  
\end{verbatim}
(same results for the four solutions).

The best is the last solution, which computes only with integers, and uses fast exponentiation of matrices, so $T(n) = O(\log(n))$.

Exercise 4.4.15* (Some combinatorics)

Answers

Comments

Exercise 4.4.15* (Some combinatorics)

Answers

Comments

Add answer