Let $t_n$ be a number of sequences
$$ 1 \le a_1 < a_2 < … < a_k \le n $$
such that $a_{2i}$ is even and $a_{2i+1}$ is odd.
Prove that $$\sum_{n} t_n x^n = \frac{x^k}{(1-x^2)^k(1-x)} $$
My attempt. I want to use there enumerators and I have 4 cases.
1. both $n$ and $k$ are even (other cases will be analogical)
Then enumerator will be $$(x+x^3+…+x^{n-1})^{k/2} (1+x^2+…+x^{n})^{k/2} = \left(x\cdot \frac{1-x^{\frac{n-1}{2}}}{1-x^2} \cdot \frac{1-x^{\frac{n}{2}}}{1-x^2} \right)^{k/2}$$
But how can I get from there my thesis?
Best Answer
We have that $$f(x):=\frac{x^k}{(1-x^2)^k(1-x)}=\frac{1}{1-x}\left(\frac{x}{1-x^2}\right)^k =\frac{1}{1-x}\left(\sum_{j=0}^{\infty}x^{2j+1}\right)^k.$$ Therefore the coefficient $t_n=[x^n]f(x)$ is the number of ways we can write a positive integer $\leq n$ as the sum of $k$ odd numbers. Now note that $a_1,a_2-a_1,\dots,a_k-a_{k-1}$ are $k$ odd numbers whose sum is $a_k$ which is $\leq n$ and such $k$ odd numbers determine in unique way a sequence $ 1 \le a_1 < a_2 < ... < a_k \le n $ such that $a_{2i}$ is even and $a_{2i+1}$ is odd.