How many nonnegative integers $x_1, x_2, x_3, x_4$ satisfy $2x_1 + x_2 + x_3 + x_4 = n$?

You can use a recurrence to solve this, as you already mentioned ( #(M) is the number of elements of the set M)

$$S(n)=#({(x_1,x_2,x_3,x_4)| x_1+x_2+x_3+x_4 =n, x_1ge 0,x_2ge 0,x_3ge 0,x_4ge 0})$$ $$E(n)=#({(x_1,x_2,x_3,x_4)| 2x_1+x_2+x_3+x_4 =n, x_1ge 0,x_2ge 0,x_3ge 0,x_4ge 0})$$ $$O(n)=#({(x_1,x_2,x_3,x_4)| (2x_1+1)+x_2+x_3+x_4 =n, x_1ge 0,x_2ge 0,x_3ge 0,x_4ge 0})$$

So $E(n)$ counts the tuples where the first component is even and $O(n)$ counts the tuples where the first component is odd.

We have $$S(n)=E(n)+O(n)$$ $S(n)$ can be calculated with the stars and bars method, we get $$S(n)={ n+3choose 3}$$

From the definitions wee see that $$O(n)=E(n-1)$$ So we get $$E(n)={ n+3choose 3}-E(n-1)$$ and further $$E(n)=sum_{i=0}^{n}{ i+3choose 3}(-1)^{n-i}$$

Note that ${ i+3choose 3}$ is a polynomial of degree $3$, so a closed formula for this sum can be derived from the Faulhaber formulas if we take into account that

$$sum_{i=0}^{2n+1}i^p(-1)^{2n+1-i}=sum_{i=0}^{2n+1}i^p-2sum_{i=0}^{n}(2i)^p=sum_{i=0}^{2n+1}i^p-2^{p+1}sum_{i=0}^{n}i^p$$ So finally we get $$E(2n+1)=frac{4 {{n}^{3}}+21 {{n}^{2}}+35 n+18}{6}$$ and $$E(2n)={ 2n+4choose 3}-E(2n+1)=frac{4 {{n}^{3}}+15 {{n}^{2}}+17 n+6}{6}$$

I would use the generating function. If $a_n$ is the number of solutions for a given $n$ then $$sum_{n=0}^infty a_n X^n=frac1{(1-X^2)(1-X)^3}=frac1{(1+X)(1-X)^4} =frac{A}{1+X}+frac{f(X)}{(1-X)^4}$$ in partial fractions where $f(X)$ is a cubic polynomial. Now find $A$ and $f(X)$ etc.