Combinatorics & Binomial

We want to expand $\frac{1+x}{(1-x{)}^2(1+x^2)}$ in powers of $x$ and identify the coefficient $a_n$ of $x^n$.

Partial fractions. Write$$\frac{1+x}{(1-x{)}^2(1+x^2)}=\frac{A}{1-x}+\frac{B}{(1-x{)}^2}+\frac{Cx+D}{1+x^2}.$$Multiplying both sides by $(1-x{)}^2(1+x^2)$ and comparing coefficients gives $A=\frac{1}{2}$, $B=1$, $C=\frac{1}{2}$, $D=-\frac{1}{2}$. So$$\frac{1+x}{(1-x{)}^2(1+x^2)}=\frac{1/2}{1-x}+\frac{1}{(1-x{)}^2}+\frac{\frac{1}{2}x-\frac{1}{2}}{1+x^2}.$$Power series for each term. Using standard binomial expansions:$$\frac{1/2}{1-x}=\frac{1}{2}\sum _{n=0}^{\infty }{x}^n,$$$$\frac{1}{(1-x{)}^2}=\sum _{n=0}^{\infty }(n+1)x^n,$$$$\frac{x/2}{1+x^2}=\frac{1}{2}\sum _{n=0}^{\infty }(-1{)}^n{x}^{2n+1},\frac{-1/2}{1+x^2}=-\frac{1}{2}\sum _{n=0}^{\infty }(-1{)}^n{x}^{2n}.$$The last two series contribute only to odd and even powers respectively, with alternating signs.

Collecting by residue mod 4. The coefficient $a_n$ receives contributions from the first two series (always $\frac{1}{2}+(n+1)$), and from the last two only when $n$ is odd or even:

- $n\equiv 0(\mathrm{mod}4)$: last two terms give $0-\frac{1}{2}(-1{)}^{n/2}=0-(-\frac{1}{2})=+\frac{1}{2}$, wait — more cleanly, the $(-1{)}^n$ factor is $+1$, so last two contribute $0-\frac{1}{2}$. Total: $\frac{1}{2}+(n+1)+0-\frac{1}{2}=n+1$.
- $n\equiv 1(\mathrm{mod}4)$: the odd-power series has $(-1{)}^{(n-1)/2}=+\frac{1}{2}$, even-power series gives $0$. Total: $\frac{1}{2}+(n+1)+\frac{1}{2}=n+2$.
- $n\equiv 2(\mathrm{mod}4)$: odd-power contributes $0$, even-power has $(-1{)}^{n/2}=-1$ so $-\frac{1}{2}\cdot (-1)=+\frac{1}{2}$. Total: $\frac{1}{2}+(n+1)+\frac{1}{2}=n+2$.
- $n\equiv 3(\mathrm{mod}4)$: odd-power has $(-1{)}^{(n-1)/2}=-1$ so $-\frac{1}{2}$, even-power contributes $0$. Total: $\frac{1}{2}+(n+1)-\frac{1}{2}=n+1$.

So $a_n=n+1$ when $n\equiv 0$ or $3(\mathrm{mod}4)$, and $a_n=n+2$ when $n\equiv 1$ or $2(\mathrm{mod}4)$.

The fraction $\frac{11000}{8181}$. Notice that$$\frac{11000}{8181}=\frac{1.1}{0.9\times 1.01}=\frac{1+x}{(1-x{)}^2(1+x^2)}{|}_{x=0.1}.$$The key insight is that $\frac{1+0.1}{(0.9{)}^2\times 1.01}=\frac{1.1}{0.81\times 1.01}=\frac{1.1}{0.8181}$, and scaling numerator and denominator by $10000$ gives $\frac{11000}{8181}$.

The series at $x=0.1$ starts $a_0+a_1\cdot 0.1+a_2\cdot 0.01+\cdots$. Using $a_n$ values: $1,3,4,4,5,7,8,8,9,11,\dots$, so$$\frac{11000}{8181}=1+3(0.1)+4(0.01)+4(0.001)+5(0.0001)+\cdots \approx 1.34457890\dots$$to nine significant figures.

We start by expanding $(1-x^6{)}^{-2}$ using the negative binomial series. Recall that $(1-u{)}^{-2}={\sum }_{n=0}^{\infty }(n+1)u^n$, so substituting $u=x^6$ gives the general term $(n+1)x^{6n}$ for $n\ge 0$.

Part (i).

We need the coefficient of $x^{24}$ in $(1-x^6{)}^{-2}(1-x^3{)}^{-1}$. The expansion of $(1-x^3{)}^{-1}$ contributes terms $x^{3k}$ for $k\ge 0$. To get a total power of $x^{24}$, we need $6n+3k=24$, i.e. $2n+k=8$, with $n,k\ge 0$. The contribution from each pair $(n,k)$ is $(n+1)\cdot 1$, so the coefficient of $x^{24}$ is$$\sum _{n=0}^4(n+1)=1+2+3+4+5=15.$$For the general coefficient of $x^m$: we need $6n+3k=m$, so $m$ must be a multiple of 3. Write $m=3j$; then $2n+k=j$ with $n\ge 0$, $k\ge 0$, giving $n$ ranging from $0$ to $\lfloor j/2\rfloor$. The coefficient is ${\sum }_{n=0}^{\lfloor j/2\rfloor }(n+1)$.

- If $m$ is not divisible by 3, the coefficient is $0$.
- If $m=6q$ (divisible by 6), write $j=2q$: the sum runs from $n=0$ to $n=q$, giving $\frac{(q+1)(q+2)}{2}$.
- If $m=6q+3$ (divisible by 3 but not 6), write $j=2q+1$: the sum runs from $n=0$ to $n=q$, giving $\frac{(q+1)(q+2)}{2}$.

In both non-zero cases with $m=6q+r$ where $$\begin{gathered} r\in \\ 0,3 \end{gathered}$$, the answer is $\frac{(q+1)(q+2)}{2}$.

Part (ii).

Now consider $f(x)=(1-x^6{)}^{-2}(1-x^3{)}^{-1}(1-x{)}^{-1}$. The key observation is that powers of $x$ in $(1-x{)}^{-1}$ that are not multiples of 3 combine with $(1-x^3{)}^{-1}$ to produce only multiples of 3 when summed; similarly, only multiples of 6 survive the further multiplication by $(1-x^6{)}^{-2}$. Rather than tracking every combination directly, note that$$f(x)=(1-x^6{)}^{-2}(1-x^3{)}^{-1}(1-x{)}^{-1}.$$The coefficient of $x^{24}$ equals the number of ways to write $24=6a+3b+c$ with $a,b,c\ge 0$, weighted by $(a+1)$. This is equivalent to summing, over all valid $(a,b,c)$, the weight $(a+1)$.

Grouping by $a$: for each $a$ from $0$ to $4$, we need $3b+c=24-6a$, i.e. $c=24-6a-3b$ with $0\le b\le (24-6a)/3$. The number of valid $(b,c)$ pairs is $\lfloor (24-6a)/3\rfloor +1=(8-2a)+1=9-2a$. So the coefficient of $x^{24}$ is$$\sum _{a=0}^4(a+1)(9-2a)=1\cdot 9+2\cdot 7+3\cdot 5+4\cdot 3+5\cdot 1=9+14+15+12+5=55.$$For $x^{25}$: we need $6a+3b+c=25$. Since $6a+3b$ is always a multiple of 3, we need $c\equiv 1(\mathrm{mod}3)$. Writing $c=3c^{\prime }+1$, we get $6a+3(b+c^{\prime })=24$, i.e. $2a+(b+c^{\prime })=8$. This has the same count of solutions as the $x^{24}$ case (with $(a,b+c^{\prime })$ in place of $(a,k)$), so the coefficient of $x^{25}$ is also $55$.

For $x^{66}$: here $6a+3b+c=66$. For each $a$ from $0$ to $11$, we need $3b+c=66-6a$, giving $(66-6a)/3+1=23-2a+1=23-2a+1$ pairs. More carefully: the number of $(b,c)$ pairs with $3b+c=66-6a$, $b,c\ge 0$ is $(66-6a)/3+1=22-2a+1=23-2a$. The coefficient of $x^{66}$ is$$\sum _{a=0}^{11}(a+1)(23-2a).$$Expanding: ${\sum }_{a=0}^{11}(23(a+1)-2a(a+1))=23\cdot \frac{12\cdot 13}{2}-2{\sum }_{a=0}^{11}a(a+1)$. We have ${\sum }_{a=0}^{11}a(a+1)={\sum }_{a=1}^{11}(a^2+a)=\frac{11\cdot 12\cdot 23}{6}+\frac{11\cdot 12}{2}=506+66=572$. So the coefficient is $23\cdot 78-2\cdot 572=1794-1144=650$.