Provide a closed formula based on the generating function $\frac{x}{1+x+x^2}$

Question

Recently, when I self-learnt Discrete Mathematics and Its Applications 8th by Kenneth Rosen, I did only the even-numbered exercises which the author offers the detailed description instead of the odd ones because the odd ones and the corresponding even ones are very similar.

I has some questions about exercise 8.4-8-g) which is related with the generating function for the recurrence relation. The problem is

For each of these generating functions, provide a closed formula for the sequence it determines.

...

g) $x/(1+x+x^2)$

The answer says

The key here is to recall the algebraic identity $1 − x^3 = (1 − x)(1 + x + x^2)$. Therefore the given function can be rewritten as $x(1 − x)/(1 − x^3)$, which can then be split into $x/(1 − x^3)$ plus $−x^2/(1 − x^3)$. From Table 1 we know that $1/(1 − x^3) = 1 + x^3 + x^6 + x^9 + \cdots$ . Therefore $x/(1 − x^3) = x + x^4 + x^7 + x^{10} + \cdots$ , and $-x^2/(1 − x^3) = -x^2 - x^5 - x^8 - x^{11} - \cdots$ . Thus we see that $a_n$ is 0 when $n$ is a multiple of 3, it is 1 when $n$ is 1 greater than a multiple of 3, and it is −1 when $n$ is 2 greater than a multiple of 3. One can check this answer with Maple.

I tried first by myself when doing this exercise without reading the answer: $$ \begin{align*} \frac{x}{1+x+x^2}&=x\cdot \sum_{n=0}^{\infty}(-x-x^2)^n\\ &=x\cdot \sum_{n=0}^{\infty}(-1)^n\cdot x^n\cdot (1+x)^n\\ &=x\cdot \sum_{n=0}^{\infty}(-1)^n\cdot x^n\cdot \sum_{k=0}^n\binom{n}{k}x^k\\ &=\sum_{n=0}^{\infty}\sum_{k=0}^n\binom{n}{k}\cdot (-1)^n\cdot x^{n+k+1}\\ \end{align*}\\ $$ Then $$ \begin{align*} a_m&=\sum_{\substack{0\le k\le n\le m-1\\n+k+1=m}}\binom{n}{k}\cdot (-1)^n\\ &=\sum_{n=\lceil\frac{m-1}{2}\rceil}^{m-1}\binom{n}{m-n-1}(-1)^n \end{align*} $$

I checked some terms for $m=3k$, $a_3=\binom{1}{1}\cdot (-1)+\binom{2}{0}\cdot 1=0$ and $a_6=\binom{5}{0}\cdot (-1)+\binom{4}{1}\cdot (1)+\binom{3}{2}\cdot (-1)=0$. Then it seems that my equation $a_m=\sum_{n=\lceil\frac{m-1}{2}\rceil}^{m-1}\binom{n}{m-n-1}(-1)^n$ is true.

Q:

Then how to prove without using the relation of my try with the book answer? $$ a_m=\sum_{n=\lceil\frac{m-1}{2}\rceil}^{m-1}\binom{n}{m-n-1}(-1)^n =\begin{cases} 0,m\equiv 0\pmod 3\\ 1,m\equiv 1\pmod 3\\ -1,m\equiv 2\pmod 3 \end{cases} $$

Answer 1

I first encountered this identity in "An Alternate Approach to Alternating Sums: A Method to DIE for" by Arthur Benjamin, where it is proved on page 197. Note that his $n$ is your $m-1$, and his sum differs from yours by a factor of $(-1)^{m-1}$. The writeup is quite readable, but I summarize the idea below.

If you parametrize your final sum by $k$ instead of $n$, the unsigned sum counts the number of square-domino tilings (hereafter $s$ and $d$) of a $1\times (m-1)$ board using $k$ dominoes (and $m-1-2k$ squares). On this set we can almost define an involution that changes the number of dominoes by $1$ as follows. Break the tiling into $(sd)^p U$ where $U$ does not start with $sd$; thus it starts with a choice of either $d$ or $ss$. The involution replaces that start of $U$ with the other choice.

This pairs up all tilings except the (at most one) where $U=\varnothing$ or $U=s$. Since all other tilings pair up with their image under the involution, they sum to zero. So we only need to check the sign of the exceptional tiling, and indeed it agrees with the formula you wrote.

Answer 2

Here we derive a closed formula for the coefficients of the generating function $A$ based upon partial fraction decomposition. We start with \begin{align*} A(x)=\frac{x}{1+x+x^2}=\frac{x}{\left(x-\omega_1\right)\left(x-\omega_2\right)} \end{align*} Since $\left(x^3-1\right)=(x-1)\left(x^2+x+1\right)$ the zeros $\omega_1$ and $\omega_2$ are the $3$rd roots of unity \begin{align*} \omega_1&=e^{\frac{2\pi i}{3}}=-\frac{1}{2}+i\frac{\sqrt{3}}{2}\\ \omega_2&=e^{-\frac{2\pi i}{3}}=-\frac{1}{2}-i\frac{\sqrt{3}}{2}=\overline{\omega_1}=\frac{1}{\omega_1}\\ \end{align*}

We apply partial fraction decomposition to $A$ and obtain \begin{align*} \color{blue}{A(x)} &=\frac{\omega_1}{\omega_1-\omega_2}\,\frac{1}{x-\omega_1} -\frac{\omega_2}{\omega_1-\omega_2}\,\frac{1}{x-\omega_2}\tag{1}\\ &=\frac{i}{\sqrt{3}}\,\frac{1}{1-\frac{x}{\omega_1}}-\frac{i}{\sqrt{3}}\,\frac{1}{1-\frac{x}{\omega_2}}\tag{2}\\ &=\frac{i}{\sqrt{3}}\sum_{n=0}^{\infty}\left(\frac{1}{\omega_1^n}-\frac{1}{\omega_2^n}\right)x^n\tag{3}\\ &=\frac{i}{\sqrt{3}}\sum_{n=0}^{\infty}\left(\omega_2^n-\omega_1^n\right)x^n\tag{4}\\ &=\sum_{n=0}^{\infty}\color{blue}{a_n}x^n\\ \end{align*} with \begin{align*} &\color{blue}{a_n= \begin{cases} 0&\qquad n\equiv 0\pmod{3}\\ 1&\qquad n\equiv 1\pmod{3}\qquad\qquad n\geq 0\\ -1&\qquad n\equiv 2\pmod{3} \end{cases}}\tag{4} \end{align*} according to the claim.

Comment:

• In (1) we make the Ansatz \begin{align*} \frac{\color{blue}{x}}{1+x+x^2}=\frac{\alpha}{x-\omega_1}+\frac{\beta}{x-\omega_2} =\frac{\color{blue}{(\alpha+\beta)x-\left(\alpha\omega_2+\beta\omega_1\right)}}{\left(x-\omega_1\right)\left(x-\omega_2\right)} \end{align*} and compare linear and constant part of the numerators.

• In (2) we use $\omega_1-\omega_2=i\sqrt{3}$ and do some rearrangements.

• In (3) we do a geometric series expansion and merge the series by collecting like terms in $x$.

• In (4) we use $\omega_1=\frac{1}{\omega_2}$.

• In (5) we obtain for $n\geq 0$: \begin{align*} \omega_2^{3n}-\omega_1^{3n}&=1-1=0\\ \omega_2^{3n+1}-\omega_1^{3n+1}&=\omega_2-\omega_1=-i\sqrt{3}\\ \omega_2^{3n+2}-\omega_1^{3n+2}&=\omega_2^2-\omega_1^2=\omega_1-\omega_2=i\sqrt{3}\\ \end{align*} Multiplication with $\frac{i}{\sqrt{3}}$ gives the wanted result in (4).

Note: In order to derive the left-hand side of OPs binomial identity it is convenient to use the coefficient of operator $[x^m]$ to denote the coefficient of $x^m$ in a series.

This way we obtain for $m\geq 1$: \begin{align*} \color{blue}{[x^m]}\color{blue}{\frac{x}{1+x+x^2}} &=[x^{m-1}]\sum_{n=0}^{\infty}(-1)^nx^n(1+x)^n\tag{6}\\ &=\sum_{n=0}^{m-1}(-1)^n[x^{m-1-n}](1+x)^n\tag{7}\\ &\,\,\color{blue}{=\sum_{n=0}^{m-1}(-1)^n\binom{n}{m-1-n}}\tag{8} \end{align*}

Comment:

• In (6) we do a geometric series expansion and apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

• In (7) we use the linearity of the coefficient of operator and apply again the rule as in (6). We also set the upper limit of the sum to $m-1$ since other terms do not contribute.

• In (8) we select the coefficient of $x^{m-1-n}$ from $(1+x)^n$. Here we use the common convention that $\binom{p}{q}=0$ if $q<0$ or $p<q$.