Compute the coefficient of $x^n$

Question

Consider the formal power series $$F(x) = \sum_{k\ge0}(x+x^2-x^3)^k$$ How can I compute the coefficient of $x^n$ in $(F(x)) ^2$?

I have already rewritten F(x) as $$F(x) = \sum_{n\ge0} [(x ^n) (2n+3+(-1)^n)/4] $$ if that helps

Answer 1

I already proved here that for $n\ge 0$ $$\frac{2n+3+(-1)^n}{4}=k+1\qquad (\ast)$$

Where $n=2k$ if $n$ is even and $n=2k+1$ if $n$ is odd.

Now when multiplying $F(x)F(x)$, the term containing $x^n$ is given by $$\sum_{i=0}^n (a_ix^i)(a_{n-i}x^{n-i})$$ So the coefficient of $x^n$ is given by $$\sum_{i=0}^n (a_i)(a_{n-i})$$

With $a_n=k+1$ as defined in $(\ast)$ $$\begin{array}{|c|c|} \hline \boldsymbol{n} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\\hline \boldsymbol{k} & 0 & 0 & 1 & 1 & 2 & 2 & 3 & 3\\\hline \boldsymbol{a_n} & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4\\\hline \end{array}$$ From here you take 2 cases, one if $n$ is even and one if $n$ is odd

Case 1: $n=2k+1$ \This case is simple to write since because we have even number of coefficients so they basically “aligns” for example if $n=7$, $k=3$ and list of coefficients is $$\begin{array}{|c|c|} \hline \boldsymbol{n} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\\hline \boldsymbol{k} & 0 & 0 & 1 & 1 & 2 & 2 & 3 & 3\\\hline \boldsymbol{a_n} & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4\\\hline \end{array}$$ so the sum becomes $$(1)(4)+(1)(4)+(2)(3)+(2)(3)+(3)(2)+(3)(2)+(4)(1)+(4)(1)$$ which can be seen as $$2[(1)(4)+(2)(3)+(3)(2)+(4)(1)]$$ so, for any $n\ge 3$, $$\Rightarrow\sum_{i=0}^n (a_i)(a_{n-i})$$ $$=2\sum_{t=1}^{k+1} (t)(k-t+2)$$ Which can be calculated using a simple summation formula

Case 2: $n=2k$ \This is a bit more calculated to write since we now have an odd number of coefficients. For example if $n=6$, $k=3$, and the list of coefficients becomes $$\begin{array}{|c|c|} \hline \boldsymbol{n} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline \boldsymbol{k} & 0 & 0 & 1 & 1 & 2 & 2 & 3 \\\hline \boldsymbol{a_n} & 1 & 1 & 2 & 2 & 3 & 3 & 4 \\\hline \end{array}$$ so the sum no longer "aligns" and becomes $$(1)(4)+(1)(3)+(2)(3)+(2)(2)+(3)(2)+(3)(1)+(4)(1)$$ which can be seen as two summations $$(1)(4)+(2)(3)+(3)(2)+(4)(1)\text{ and } (1)(3)+(2)(2)+(3)(1)$$ So, for any $n\ge 3$, $$\sum_{i=0}^n (a_i)(a_{n-i})$$ $$=\sum_{t=1}^{k+1} (t)(k-t+2)+\sum_{t=1}^{k}(t)(k-t+1)$$ Which can also be calculated using a simple summation formula

Hope this helps