I have the generating function $g(x) = \Sigma^\infty_{n=0}b_nx^n = \frac{1}{(1-x)^2(1-x^2)}$ and I'm asked to find the explicit formula for the sequence. After I split the fraction into two sums and reverted each sum into a summation expression, I could not figure out how to continue because the expression seemed tricky.
After I looked at the answer, the author took a different approach by saying that the expression can be rewritten as $\frac{1}{1-x}\cdot \frac{1}{1-x}\cdot \frac{1}{1-x^2}$, which equals $(\Sigma^\infty_{a=0}x^a)\cdot(\Sigma^\infty_{b=0}x^b)\cdot(\Sigma^\infty_{c=0}x^{2c})$, which would count all non-negative integer solutions for the equation $a + b + 2c = n$.
He then says that since $c \leq \lfloor n/2 \rfloor$, we it also equals to the amount of solutions for $a + b = n - 2k + 1$.
My problem is that then he says that now we can count all the solutions for the pairs $(a,b)$ which solve for the above, $\forall k\in \{0, 1, 2, \ldots, \lfloor n/2 \rfloor\}$, and the expression he uses to represent that is:
$$ \Sigma^{\lfloor n/2 \rfloor}_{k = 0} (n -2k + 1)$$
At first I didn't understand why the answer is this arithmetic sequence. I knew that the amount of different non-negative integer pairs $(a,b)$ such that $a+b = n$ is $\binom{n + 2 - 1}{2 - 1} = \binom{n + 1}{1}$, so put in our example I got:
$$\Sigma^{\lfloor n/2 \rfloor}_{k=0}\binom{n - 2k + 1 + 2 }{2 - 1} = \Sigma^{\lfloor n/2 \rfloor}_{k=0}\binom{n - 2k + 2}{1} =\Sigma^{\lfloor n/2 \rfloor}_{k=0}(n - 2k + 2)$$
The two don't match up.
While this combinatorial approach is perfectly good, there's a standard approach based on the partial fraction decomposition $$ \frac1{(1 - x)^2 (1 - x^2)} = \frac{1}{8 (1+x)}+\frac{1}{8 (1-x)}+\frac{1}{4 (1-x)^2}+\frac{1}{2 (1-x)^3}. $$ The point is that each of the terms resulting from partial fractions (fortunately there are no irreducible quadratics here) have standard Taylor series: \begin{align*} \frac{1}{1+x} &= \sum_{n=0}^\infty (-1)^n x^n \\ \frac{1}{1-x} &= \sum_{n=0}^\infty x^n \\ \frac{1}{(1-x)^2} &= \sum_{n=0}^\infty (n+1) x^n \\ \frac{1}{(1-x)^3} &= \sum_{n=0}^\infty \frac{(n+2)(n+1)}2 x^n. \end{align*} Therefore \begin{align*} \frac1{(1 - x)^2 (1 - x^2)} &= \frac18 \sum_{n=0}^\infty (-1)^n x^n + \frac18 \sum_{n=0}^\infty x^n + \frac14 \sum_{n=0}^\infty (n+1) x^n + \frac12 \sum_{n=0}^\infty \frac{(n+2)(n+1)}2 x^n \\ &= \sum_{n=1}^\infty \frac{2 n^2+8 n+7+(-1)^n}8 x^n, \end{align*} and therefore $$ b_n = \frac{2 n^2+8 n+7+(-1)^n}8. $$