$n$-words over the alphabet $\{0,...,d\}$ without consecutive $0$'s

Question

I'm trying to solve the following problem in chapter 3 of Aigner's A Course in Enumeration:

Let $f(n)$ be the number of $n$-words over the alphabet $\{0,1,2\}$ that contain no neighboring 0's. Determine $f(n)$.

One is easily led to the recurrence $f(n)=2(f(n-1)+f(n-2))$ and the generating function $$F(x)=\frac{1+x}{1-2x-2x^2}.$$ At this point, I am trying to solve for $f(n)$. I used partial fractions to get $$f(n)=\frac{1+\sqrt{3}}{2\sqrt{3}}(\frac{-1+\sqrt{3}}{2})^n+\frac{-1+\sqrt{3}}{2\sqrt{3}}(\frac{-1-\sqrt{3}}{2})^n$$ for $n\geq 2$, but I cannot reconcile this with Brian M. Scotts answer here: Recurrence relation for the number of ternary strings containing 2 consecutive zeros vs not containing

I also tried generalizing, by looking at the $n$-words over $\{0,...,m\}$ with no consecutive $0$'s. This leads one to the generating function $$F_m(x)=\frac{1+x}{1-mx-mx^2}.$$ Since my determination of $f(n)$ gives incorrect values, I made a mistake. After an hour of checking, I just cannot find it. Furthermore, Aigner gives the following answer $$f(n)=\sum_i(\binom{n+1}{2i+1}+\binom{n}{2i+1})3^i,$$ which cannot come from this fibonacci-like approach. Any ideas?

Answer 1

Start with $${1+x\over 1-2x-2x^2}={\left({{1\over 2}+{1\over\sqrt{3}}}\right)\over 1-x(1+\sqrt{3}) }+{\left({{1\over 2}-{1\over\sqrt{3}}}\right)\over 1-x(1-\sqrt{3}) } $$ to get
\begin{eqnarray*}p(n)&=&\left({{1\over 2}+{1\over\sqrt{3}}}\right)(1+\sqrt{3})^n+\left({{1\over 2}-{1\over\sqrt{3}}}\right)(1-\sqrt{3})^n\\[5pt]&=&{1\over 2}[(1+\sqrt{3})^n+(1-\sqrt{3})^n]+{1\over\sqrt{3}}[(1+\sqrt{3})^n-(1-\sqrt{3})^n]\\[5pt] &=&\sum_j {n\choose 2j}\,3^j+\sum_j 2{n\choose 2j+1}\,3^j. \end{eqnarray*}

Answer 2

It looks to me that you, Aigner and Brian Scott are all saying the same thing.

We have $f(n) = 2 f(n-1) + 2 f(n-2)$, together with $f(1)=3$ and $f(2)=8$, hence:

$$ \sum_{n\geq 1}f(n)\,x^n = \frac{3x+2x^2}{1-2x-2x^2}$$ and by partial fraction decomposition: $$ f(n) = \left(11+\frac{14}{\sqrt{3}}\right)\left(\frac{-1+\sqrt{3}}{2}\right)^n + \left(11-\frac{14}{\sqrt{3}}\right)\left(\frac{-1-\sqrt{3}}{2}\right)^n. $$ In order to recover Aigner's representation as a weighted sum of binomial coefficients, it is enough to expand $(-1\pm\sqrt{3})^n$ by using the binomial theorem.

Answer 3

Here is another variation of the theme. It's not the shortest one, but it could be helpful for similar cases and it provides a slightly different representation of the solution.

Since we often have to cope with series of the form

\begin{align*} G(x)=\frac{p+qx}{ax^2+bx+c} \end{align*}

we derive a general representation by a series expansion at $x=0$. Based upon this result we obtain a solution for $F(x)$ and $F_m(x)$.

Using partial fraction decomposition of $G(x)$ and denoting the zeros of $ax^2+bx+c$ with $x_0,x_1$ we obtain

\begin{align*} G(x)&=\frac{p+qx}{ax^2+bx+c}\\ &=\frac{1}{a}\frac{p+qx_0}{x_0-x_1}\frac{1}{x-x_0}-\frac{1}{a}\frac{p+qx_1}{x_0-x_1}\frac{1}{x-x_1}\tag{1}\\ &=\frac{1}{ax_0}\frac{p+qx_0}{x_1-x_0}\frac{1}{1-\frac{x}{x_0}} -\frac{1}{ax_1}\frac{p+qx_1}{x_1-x_0}\frac{1}{1-\frac{x}{x_1}}\\ &=\frac{1}{ax_0}\frac{p+qx_0}{x_1-x_0}\sum_{k=0}^{\infty}\left(\frac{x}{x_0}\right)^k -\frac{1}{ax_1}\frac{p+qx_1}{x_1-x_0}\sum_{k=0}^{\infty}\left(\frac{x}{x_1}\right)^k\tag{2}\\ &=\frac{x_1}{c}\frac{p+qx_0}{x_1-x_0}\sum_{k=0}^{\infty}\left(\frac{a}{c}x_1\right)^kx^k -\frac{x_0}{c}\frac{p+qx_1}{x_1-x_0}\sum_{k=0}^{\infty}\left(\frac{a}{c}x_0\right)^kx^k\tag{3} \end{align*}

Comment:

• In (1) we use partial fraction decomposition and $$ax^2+bx+c=a(x-x_0)(x-x_1)=a(x^2-(x_0+x_1)x+x_0x_1)$$

• In (2) we represent the fractions as geometric series at $x=0$.

• In (3) we use the relationship $x_0x_1=\frac{c}{a}$

In the following we use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of the series in (3)

\begin{align*} [x^n]G(x)&=\frac{p+qx_0}{x_1-x_0}a^n\left(\frac{x_1}{c}\right)^{n+1} -\frac{p+qx_1}{x_1-x_0}a^n\left(\frac{x_0}{c}\right)^{n+1}\\ &=\frac{a^n}{c^{n+1}}\frac{1}{x_1-x_0}\left[(p+qx_0)x_1^{n+1}-(p+qx_1)x_0^{n+1}\right] \end{align*}

Now it's time to harvest. With \begin{align*} F(x)&=\frac{p+qx}{ax^2+bx+c}=\frac{1+x}{-2x^2-2x+1} \end{align*} we obtain \begin{align*} x_{0,1}&=\frac{1}{2a}\left(-b\pm\sqrt{b^2-4ac}\right)=-\frac{1}{2}(1\pm\sqrt{3})\\ x_1-x_0&=\sqrt{3}\\ p+qx_0&=\frac{1}{2}(1-\sqrt{3})\\ p+qx_1&=\frac{1}{2}(1+\sqrt{3}) \end{align*} and we derive the coefficient $[x^n]F(x)$ as \begin{align*} [x^n]F(x)&=(-2)^n\frac{1}{\sqrt{3}}\left[\frac{1}{2}(1-\sqrt{3})\left(-\frac{1}{2}\right)^{n+1}(1-\sqrt{3})^{n+1}\right.\\ &\qquad\qquad\qquad\left.-\frac{1}{2}(1+\sqrt{3})\left(-\frac{1}{2}\right)^{n+1}(1+\sqrt{3})^{n+1}\right]\\ &=\frac{1}{4\sqrt{3}}\left[(1+\sqrt{3})^{n+2}-(1-\sqrt{3})^{n+2}\right]\\ &=\frac{1}{4\sqrt{3}}\sum_{j}2\binom{n+2}{2j+1}\left(\sqrt{3}\right)^{2j+1}\\ &=\frac{1}{2}\sum_{j}\binom{n+2}{2j+1}3^j\tag{4} \end{align*}

Note, that from (4) and OPs representation we obtain the identity

\begin{align*} \frac{1}{2}\sum_{j}\binom{n+2}{2j+1}3^j=\sum_{j}\left[\binom{n+1}{2j+1}+\binom{n}{2j+1}\right]3^j \end{align*}

$$ $$

Similarly we obtain from the generating function \begin{align*} F_m(x)=\frac{1+x}{-mx^2-mx+1} \end{align*}

the coefficient $[x^n]$ of $F_m$:

\begin{align*} [x^n]F_m(x)&=\frac{\left(\frac{m}{2}\right)^n}{4\sqrt{1+\frac{4}{m}}} \left[\left(1+\sqrt{1+\frac{4}{m}}\right)^{n+2}-\left(1-\sqrt{1+\frac{4}{m}}\right)^{n+2}\right]\\ &=\frac{1}{2}\left(\frac{m}{2}\right)^n\sum_{j}\binom{n+2}{2j+1}\left(1+\frac{4}{m}\right)^j \end{align*}

Note: With the help of Wolfram Alpha we find \begin{align*} F(x)=\frac{1+x}{-2x^2-2x+1}=1+3x+8x^2+22x^3+60x^4+164x^5+\mathcal{O}(x^6) \end{align*} Regarding a comment, note the generating function of Jack D'Aurizio is \begin{align*} H(x)&=\frac{3x+2x^2}{-2x^2-2x+1}\\ &=F(x)-1\\ &=3x+8x^2+22x^3+60x^4+164x^5+\mathcal{O}(x^6) \end{align*}