Number of solutions of $x_1+2\cdot x_2+2\cdot x_3 = n$

Question

I have to find number of solutions of $x_1+2\cdot x_2+2\cdot x_3 = n$. I guess it would be $[x^n](1+x+x^2 \dots)(1 + x^2 + x^4 \dots)^2$, but how to compute it? I know only that $\frac{1}{1-x} = 1+x+x^2 \dots$.

Answer 1

If $n$ is odd, then $x_1$ must be odd, and if $n$ is even, then $x_1$ must be even. Thus there is an integer $y$ such that $x_1=2y+1$ for former and $x_1=2y$ for latter. Thus $$ y+x_2+x_3=\frac{n-1}{2}\text{ or }y+x_2+x_3=\frac{n}{2}. $$ Therefore, the answer is \begin{align} \binom{\frac{n+3}{2}}{\frac{n-1}{2}} &= \binom{\frac{n+3}{2}}{2}\\ &=\frac{n+3}{2}\cdot\frac{n+1}{2}\cdot\frac{1}{2} \end{align} for odd $n$ and \begin{align} \binom{\frac{n+4}{2}}{\frac{n}{2}}&=\binom{\frac{n+4}{2}}{2}\\ &=\frac{n+4}{2}\cdot\frac{n+2}{2}\cdot\frac{1}{2} \end{align} for even $n$.

Answer 2

Generating Function

The generating function is $$ \begin{align} \frac1{(1-x)\left(1-x^2\right)^2} &=\frac1{(1-x)^3(1+x)^2}\\ &=\sum_{j=0}^\infty\binom{-3}{j}(-x)^j\sum_{k=0}^\infty\binom{-2}{k}x^k\\ &=\sum_{j=0}^\infty\binom{j+2}{2}x^j\sum_{k=0}^\infty\binom{k+1}{1}(-x)^k\\ &=\sum_{n=0}^\infty\sum_{k=0}^n(-1)^k\binom{k+1}{1}\binom{n-k+2}{2}x^n\tag{1} \end{align} $$ Thus, the number of solutions is $$ \bbox[5px,border:2px solid #C0A000]{\sum_{k=0}^n(-1)^k\binom{k+1}{1}\binom{n-k+2}{2}=\frac{2n^2+10n+11+(-1)^n(2n+5)}{16}}\tag{2} $$

---

Alternating Sums of Powers

To compute the sum in $(2)$ we have used the following $$ \begin{align} \sum_{k=0}^n(-1)^k1&=\frac{(-1)^n+1}2\tag{3}\\ \sum_{k=0}^n(-1)^kk&=\frac{(-1)^n(2n+1)-1}4\tag{4}\\ \sum_{k=0}^n(-1)^kk^2&=\frac{(-1)^n\left(n^2+n\right)}2\tag{5}\\ \sum_{k=0}^n(-1)^kk^3&=\frac{(-1)^n\left(4n^3+6n^2-1\right)+1}8\tag{6} \end{align} $$

---

Recursion for the Alternating Sums of Powers

The formulas in $(3)$-$(6)$ were derived by induction and $(9)$.

Combining the following two sums by reindexing the first gives $$ \begin{align} \sum_{k=0}^n(-1)^{k+1}(k+1)^m+\sum_{k=0}^n(-1)^kk^m &=\sum_{k=1}^{n+1}(-1)^kk^m+\sum_{k=0}^n(-1)^kk^m\\ &=(-1)^{n+1}(n+1)^m+2\sum_{k=0}^n(-1)^kk^m\tag{7}\\ \end{align} $$ Combining the same two sums without reindexing gives $$ \sum_{k=0}^n(-1)^{k+1}(k+1)^m+\sum_{k=0}^n(-1)^kk^m =\sum_{k=0}^n(-1)^{k+1}\left((k+1)^m-k^m\right)\tag{8} $$ Equating the right sides of $(7)$ and $(8)$ gives $$ \sum_{k=0}^n(-1)^kk^m =\frac12\left[(-1)^n(n+1)^m-\sum_{k=0}^n(-1)^k\left((k+1)^m-k^m\right)\right]\tag{9} $$