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

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

• For me it looks like a differentiation of $\log (1 + x + x^2)$. Dec 28, 2023 at 4:50
• @dEmigOd Thanks for your comment. But it seems to be similar to the above process. Do you have one better process to solve based on your method? Here is my understanding: $(\log(1+x+x^2))'=\frac{1+2\cdot x}{1+x+x^2}=2G(x)+\frac{1}{1+x+x^2}$ (here $G(x)$ is what to solve). Then $$LHS=(\sum_{n=0}^{\infty}\frac{(-1)^{n+1}}{n}x^n(1+x)^n)'=(\sum_{n=0}^{\infty}\frac{(-1)^{n+1}}{n}x^n(\sum_{k=0}^n\binom{n}{k}x^k))'=\sum_{n=0}^{\infty}\sum_{k=0}^n\frac{(-1)^{n+1}}{n}(n+k)\binom{n}{k}x^{n+k-1}.$$ Dec 28, 2023 at 5:58
• Then LHS has $$a_m^{(1)}=\sum_{\substack{k\le n\\n+k-1=m}}\frac{(m+1)(-1)^{n+1}}{n}\binom{n}{k=m+1-n}\overset{\text{change the subcript}}{=}\sum_{n=\lceil\frac{m+1}{2}\rceil}^{m+1}\cdots.$$ For RHS, $$RHS-2G(x)=\sum_{n=0}^{\infty}\sum_{k=0}^n\binom{n}{k}\cdot (-1)^n\cdot x^{n+k}\Rightarrow a_m^{(2)}=\sum_{n=\lceil\frac{m}{2}\rceil}^{m}(-1)^{n}\binom{n}{m-n}.$$ Dec 28, 2023 at 5:59
• Then for $G(x)$, $$a_m=\frac{a_m^{(1)}-a_m^{(2)}}{2}=\frac{\sum_{n=\lceil\frac{m+1}{2}\rceil}^{m+1}(-1)^{n+1}(\binom{n}{m-n}+\frac{(m+1)\binom{n}{m+1-n}}{n})}{2}=\frac{\sum_{n=\lceil\frac{m+1}{2}\rceil}^{m+1}(-1)^{n+1}\binom{n}{m+1-n}(\frac{2n-m}{m+1-n}+\frac{(m+1)}{n})}{2}\text{ when }\lceil\frac{m+1}{2}\rceil=\lceil\frac{m}{2}\rceil$$. It seems that $\frac{2n-m}{m+1-n}+\frac{(m+1)}{n}$ can't be factorized which can be verified in sympy factor((2*n-m)*n+(m+1)*(m+1-n)). Then how to proceed further? Dec 28, 2023 at 6:48
• I think this is a duplicate of math.stackexchange.com/questions/3053514/… Dec 29, 2023 at 6:41

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.

• To help future readers understanding this problem, I add some description based on that I read this paper for the 1st time. 1. The key idea for the method D.I.E is that I(Involution) which constructs one-to-one correspondence relation between adjacent terms. (This idea is also referred to in the book I'm reading although it doesn't use one terminology for that.). When failure, it considers Exception. 2. For the starting 2 single locations, $n-k$ tiles (i.e. dominos or squares) can only start with $s$ or $d$, then $s$ or $d$ if starting with $s$. So only 3 possible permutations. Dec 28, 2023 at 13:01
• 3. $n=6t$: the sole $T=(sd)^{2t}$ implies only $1$ in $\binom{n-k}{k},k=2t$, so it contributes $(-1)^k=1$. The rest is similar. 4. Related with the equation in my question as the answer author says $n=m-1$, then $a_m=\sum_{k\ge 0}\binom{n-k}{k}(-1)^{n-k}=(-1)^n\sum_{k\ge 0}\binom{n-k}{k}(-1)^{k}$. Change the formula in the paper based on $(-1)^{n=m-1}$, we can get the equation in the question. Dec 28, 2023 at 13:04
• Thanks, I think those are valuable additions here! Dec 28, 2023 at 18:18

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.

• 1. Although this solution doesn't directly solve with my equation $\sum_{n=\lceil\frac{m-1}{2}\rceil}^{m-1}\binom{n}{m-n-1}(-1)^n$, thanks for your general solution to this type of problems anyway. The book I was reading explicitly says it doesn't consider complex number situations although I have studied complex analysis before. 2. One small comment: the above partial fraction decomposition $\frac{w_1}{w_1-w_2}$ is got by solving the symbolic equation if someone tries to use the specific values of $w_1,w_2$ and does a lot of detailed calculation. Dec 29, 2023 at 3:24
• @zgc: You're welcome. I have added some information to show that the partial fraction decomposition is not too difficult to calculate here. I have also added a hint on how to derive the left-hand side of the binomial identity a little more conveniently. Dec 29, 2023 at 7:56
• 1. I said something with ambiguity. "the above partial fraction decomposition $\frac{w_1}{w_1−w_2}$ is got by solving the symbolic equation if someone tries to use the specific values of $w_1,w_2$ and does a lot of detailed calculation." means that "if someone tries ... a lot of detailed calculation" with $-\frac{1}{2}\pm i\frac{\sqrt{3}}{2}$, then he can use one easier method by direct "symbolic equation" with $w_1,w_2$. 2. Your clarification of "the left-hand side" is helpful. Dec 29, 2023 at 8:32