weak compositions of $n$ with $2m$ parts and extra conditions A weak composition of $n$ into $k$ parts is a sum 
$$\displaystyle \sum_{i=0}^k x_i=n$$ 
such that $x_i\in \mathbb{Z}$ and $x_i\geq 0$ for each $i$. 
I am trying to figure out the number of weak compositions of $n$ into $2m$ parts such that $x_i\in \left\{0,1 \right\}$ for each $i\in \left\{1, 2, \ldots, m \right\}$ and $x_i$ is even for each $i\in \left\{m+1, m+2, \ldots, 2m \right\}$.
I have decided to break my argument into two cases: 1) n is even; 2) n is odd.
1) When $n$ is even, there must be an even number of $x_i$s for $i\in \left\{1, \ldots, m \right\}$.
2) When $n$ is odd, there must be an odd number of $x_i$s for $i\in \left\{1, \ldots, m \right\}$.
What I am considering is basing my argument on the number of terms $x_i$ for $i\in \left\{1, \ldots, m \right\}$ that are equal to $1$. I can subtract them from both sides and consider the number of weak compositions of $n-x$ ($x$ is the number of $x_i$s that are equal to 1). I just can't figure out how many such compositions there are. Help me! Thank you!!
 A: I am going to assume that the $\sum\limits_{i=0}^{k}$ should be a $\sum\limits_{i=1}^{k}$, since you lay no condition on $x_0$ and since starting with $x_0$ would fly in the face of the notation "weak composition of $n$ into $k$ parts".
Before I sketch the proof, let me remind you that
(1) the number of weak compositions of a nonnegative integer $n$ into $k$ parts equals $\dbinom{n+k-1}{n}$
(this is Theorem two in the Wikipedia article "Stars and Bars", as of 11 May 2015). Hence,
(2) the number of weak compositions $\left(u_1, u_2, \ldots, u_k\right) \in \left\{0, 2, 4, \ldots\right\}^k$ of $n$ into $k$ even parts is $\dbinom{\dfrac{n}{2}+k-1}{\dfrac{n}{2}}$ if $n$ is even and $0$ if $n$ is odd.
(Indeed, this is clear when $n$ is odd, because the odd integer $n$ cannot be a sum $u_1 + u_2 + \cdots + u_k$ of even integers. When $n$ is even, the statement (2) follows by applying (1) to $\dfrac{n}{2}$ instead of $n$, and observing that the weak compositions $\left(u_1, u_2, \ldots, u_k\right) \in \left\{0, 2, 4, \ldots\right\}^k$ of $n$ into $k$ even parts are in bijection with the weak compositions of $\dfrac{n}{2}$ into $k$ parts (namely, this bijection sends each $\left(u_1, u_2, \ldots, u_k\right) \in \left\{0, 2, 4, \ldots\right\}^k$ to $\left(u_1/2, u_2/2, \ldots, u_k/2\right)$). Thus, (2) always holds.)
Now, let me fix $n$ and $m$. We define a wition to mean a weak composition of $n$ into $2m$ parts satisfying your condition. Then, there are two ways to count the witions:
1. In order to choose a wition $\left(x_1, x_2, \ldots, x_{2m}\right)$, we first choose the value $u$ of $x_1 + x_2 + \cdots + x_m$ (this is an integer between $0$ and $n$), then choose a weak composition $\left(x_1, x_2, \ldots, x_m\right) \in \left\{0, 1\right\}^m$ of $u$ into $m$ parts with all parts belonging to $\left\{0,1\right\}$ (this can be done in $\dbinom{u}{m}$ ways), and then choose a weak composition $\left(x_{m+1}, x_{m+2}, \ldots, x_{2m}\right) \in \left\{0, 2, 4, \ldots\right\}^m$ of $n - u$ into $m$ even parts (this can be done in $\dbinom{\dfrac{n-u}{2}+m-1}{\dfrac{n-u}{2}}$ ways if $n-u$ is even, and in $0$ ways if $n-u$ is odd (because of (2))), thus obtaining a wition $\left(x_1, x_2, \ldots, x_{2m}\right)$. So in total there are $\sum\limits_{\substack{u \in \left\{0, 1, \ldots, n\right\}; \\ n-u \text{ is even}}} \dbinom{u}{m} \dbinom{\dfrac{n-u}{2}+m-1}{\dfrac{n-u}{2}}$ witions.
2. In order to choose a wition $\left(x_1, x_2, \ldots, x_{2m}\right)$, we first choose a weak composition $\left(y_1, y_2, \ldots, y_m\right)$ of $n$ into $m$ parts (this can be done in $\dbinom{n+m-1}{n}$ ways (because of (1))), and then define the wition $\left(x_1, x_2, \ldots, x_{2m}\right)$ uniquely by requiring $x_i + x_{m+i} = y_i$ for every $i \in \left\{1, 2, \ldots, m\right\}$. This indeed determines the wition uniquely, because every $y_i$ can be written uniquely as a sum of an element of $\left\{0,1\right\}$ (which is what we want $x_i$ to be) and an even nonnegative integer (which is what we want $x_{m+i}$ to be). So we have $\dbinom{n+m-1}{n}$ witions in total.
Comparing these counts, we obtain $\sum\limits_{\substack{u \in \left\{0, 1, \ldots, n\right\}; \\ n-u \text{ is even}}} \dbinom{u}{m} \dbinom{\dfrac{n-u}{2}+m-1}{\dfrac{n-u}{2}} = \dbinom{n+m-1}{n}$, which, I guess, is a nice identity. (This identity can also be shown by comparing coefficients of $x^n$ in the identity $\left(\dfrac{1}{1-x}\right)^m = \left(1+x\right)^m \left(\dfrac{1}{1-x^2}\right)^m$. But this is more or less the double-counting proof we did above, just rewritten using algebra. Indeed, comparing coefficients in $\dfrac{1}{1-x} = \left(1+x\right) \cdot \dfrac{1}{1-x^2}$ gives us precisely the statement that every nonnegative integer can be uniquely written as a sum of an element of $\left\{0,1\right\}$ and an even nonnegative integer. Taking $m$-th powers corresponds to "copypasting" this argument $m$ times to get a bijection between $m$-tuples and $2m$-tuples. Comparing coefficients of $x^n$ means restricting ourselves to $m$-tuples/$2m$-tuples whose sum is $n$.)
