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

Mathematics Asked by Ivar the Boneless on December 13, 2020

Can anyone give some hints about the following question?

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

Normally this kind of question uses stars and bars but there are $$2x_1$$, which I don’t know how to handle. Help please!

Ps :I think may be we can use recurrence relation.

One idea is to deal with $$x_1$$ separately in order to use stars and bars on $$x_2,x_3,x_4$$. For example you fix $$x_1=0$$ and then you have $$x_2+x_3+x_4=n$$ or you fix $$x_1=1$$ and then get $$x_2+x_3+x_4=n-2$$ and so on and so forth. This then generates the summations $$x_2+x_3+x_4=n-2i$$ which have $${n-2i+2 choose 2}$$ solutions. Thus as $$x_1$$ can be a number between $$0$$ and $$lfloor n/2rfloor$$ you get the summation $$sum_{i=0}^{lfloor n/2rfloor}{n-2i+2 choose 2}.$$

Correct answer by b00n heT on December 13, 2020

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}$$

Answered by miracle173 on December 13, 2020

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.

Answered by Angina Seng on December 13, 2020

Related Questions

Fourier expansions of Eisenstein series as a Poincare series for the Fuchsian group

1  Asked on January 7, 2022 by lww

Is eigenvalue multiplied by constant also an eigenvalue?

1  Asked on January 7, 2022 by ruby-cho

Can someone explain the proof of the following linear differential equation

3  Asked on January 7, 2022 by lucas-g

Matroid induced by a matrix where a circuit’s nullspace is spanned by a non-negative vector

1  Asked on January 7, 2022 by kaba

Area between parabola and a line that don’t intersect? 0 or infinity

1  Asked on January 5, 2022

Positive integer solutions to $frac{1}{a} + frac{1}{b} = frac{c}{d}$

3  Asked on January 5, 2022

Are all complex functions onto?

4  Asked on January 5, 2022 by truth-seek

Proving Euler’s Totient Theorem

3  Asked on January 5, 2022

Why is identity map on a separable Hilbert space not compact? False proof.

1  Asked on January 5, 2022

Finding a general way to construct least degree polynomial having rational coefficient having irrational roots

1  Asked on January 5, 2022

Checking the MLE is consistent or not in $mathcal{N}(theta,tautheta)$.

1  Asked on January 5, 2022 by confuse_d

Conditions on inequalities $a>b$ and $b<c$ to deduce $a<c.$

3  Asked on January 5, 2022

Are $mathbb{C}-mathbb{R}$ imaginary numbers?

2  Asked on January 5, 2022 by unreal-engine-5-coming-soon

Show that $|uv^T-wz^T|_F^2le |u-w|_2^2+|v-z|_2^2$

3  Asked on January 5, 2022

Let $f,g$ be holomorphic function in $mathbb{D}$ that are continuous in $overline{mathbb{D}}$. Show that if $f=g$ on $|z|=1$, then $f=g$

1  Asked on January 5, 2022

What is the Fourier transform of the bump function $e^{-frac{1}{1-|x|^2}}$?

0  Asked on January 5, 2022 by medo

What is the valus of this integral?

0  Asked on January 5, 2022 by bachamohamed

Why are the limits of integration set as they are for the Laplace Transform?

1  Asked on January 5, 2022 by jonathan-x

Finding the local extrema of $f(x, y) = sin(x) + sin(y) + sin(x+y)$ on the domain $(0, 2 pi) times (0, 2 pi)$

2  Asked on January 5, 2022

Sum $sum_{(k_1, k_2, k_3): k_1+k_2+k_3=K, ,, n_1+n_2+n_3=N}k_1^{n_1}times k_2^{n_2} times k_3^{n_3}$

0  Asked on January 5, 2022