# Number of Non negative integer solutions of $x+2y+5z=100$

Find Number of Non negative integer solutions of $$x+2y+5z=100$$

My attempt:

we have $$x+2y=100-5z$$

Considering the polynomial $$f(u)=(1-u)^{-1}\times (1-u^2)^{-1}$$

$$\implies$$

$$f(u)=\frac{1}{(1-u)(1+u)}\times \frac{1}{1-u}=\frac{1}{2} \left(\frac{1}{1-u}+\frac{1}{1+u}\right)\frac{1}{1-u}=\frac{1}{2}\left((1-u)^{-2}+(1-u^2)^{-1}\right)$$

we need to collect coefficient of $$100-5z$$ in the above given by

$$C(z)=\frac{1}{2} \left((101-5z)+odd(z)\right)$$

Total number of solutions is

$$S(z)=\frac{1}{2} \sum_{z=0}^{20} 101-5z+\frac{1}{2} \sum_{z \in odd}1$$

$$S(z)=540.5$$

what went wrong in my analysis?

• I probably do understand your attempt, which is a nice method, but I'm not sure 100% I do. Could you please write more details and explain it better? – user126154 Nov 26 '18 at 15:14
• You get an extra coefficient of $1$ from the $(1-u^2)^{-1}$ term if $100-5z$ is even, which is when $z$ is even. So the final term in your sum should be $\frac{1}{2}\sum_{z \in even}1$ over $z=0$ to $z=20$ which gives you an extra $0.5$ and a final answer of $541$. – gandalf61 Nov 26 '18 at 15:55

An alternative way.

Given $$x+2y+5z=100$$ and it is clear that $$0\le z\le20$$.

For any possible values of $$z$$, $$x+2y=100-5z$$.

Let us take $$p=100-5z\ge0$$. Solving the equation $$x+2y=p$$, $$(-p,p)$$ is a solution. The general solution of $$(x,y)$$ is $$x=-p+2q,\ \ y=p-q,\ \ q\in\mathbb{Z}$$

If $$p=2k$$, then $$k=\dfrac p2\le q\le p=2k$$.

So, there are $$k+1=\dfrac p2+1$$ solutions for $$(x,y)$$

So, we have the following numbers as follows $$p=100,95,90,85,80,75,......,15,10,5,0$$and$$k+1=51,48,46,43,41,38,......,8,6,3,1$$

The total number of solutions are $$4(10+20+30+40)+5(8+6+3+1)+51=541$$

• ok nice what is the mistake in my solution – Umesh shankar Nov 26 '18 at 15:27
• @keyflex, I don't know why my answer is different from yours. – xpaul Nov 26 '18 at 16:05

I will find number of solutions of equation $$5x+2y+z=10 n$$ in general:

clearly the positive solutions $$x_0, y_0, z_0$$ of this equation are corespondent to the solution $$x_0+2,y_0, z_0$$ of equation $$5x+2y+z=10(n+1)$$.Clearly for $$x=>2$$, finding the solutions of $$5x+2y+z=10(n+1)$$ will lead to finding the solution of first equation,provided we consider $$x-2$$ in first equation.
If the number of solutions of equation $$5x+2y+z=10(n+1)$$ is $$\phi(n+1)$$ and that of equation $$5x+2y+z=10n$$ is $$\phi(n)$$ the difference of $$\phi(n+1)$$ and $$\phi(n)$$ is equal to the number of solutions of equation $$5x+2y+z=10(n+1)$$ for $$x=0$$ and $$x=1$$. But this equation has $$5n+6$$ solutions for $$x=0$$, (i.e. $$0= and it has $$5n+3$$ solutions for $$x=1$$, (i.e $$0=. Therefore we have:

$$\phi(n+1)-\phi(n)=10n+9$$

We can also search and find that $$\phi(1)=10$$, so we can write:

$$\phi(1)=10$$

$$\phi(2)-\phi(1)=10\times 1+9$$

$$\phi(3)-\phi(2)=10\times 2+9$$ .

.

.

$$\phi(n)-\phi(n-1)=10(n-1)+9$$

Summing theses relations gives:

$$\phi(n)=5n^2 +4n +1$$

In your question $$n=10$$, therefore number of solutions is $$\phi(10)=5.10^2+4.10+1=541$$

Note that the number of non-negative integer solutions of the following equation $$x+y=n$$ is $$n+1$$. Here $$n$$ is a non-negative integer. Clearly $$5|(x+2y)$$. Let $$x+2y=5k\tag{1}$$ where $$0\le k\le 20$$. For (1), if $$k$$ is odd, then so is $$x$$, and if $$k$$ is even, then so is $$x$$.

Case 1: $$k$$ is odd. Let $$k=2n-1$$ and $$x=2m-1$$. Then $$1\le n\le 10$$ and (1) becomes $$m+y=5n-2$$ whose number of non-negative integer solutions is $$5n-1$$.

Case 2: $$k$$ is even. Let $$k=2n$$ and $$x=2m$$. Then $$0\le n\le 10$$ and (1) becomes $$m+y=5n$$ whose number of non-negative integer solutions is $$5n+1$$.

Thus the number of non-negative integer solutions is $$\sum_{n=1}^{10}(5n-1)+\sum_{n=0}^{10}(5n+1)=551$$

Given: $$x+2y=100-5z$$, tabulate: $$\begin{array}{c|c|c} z&x&\text{count}\\ \hline 0&100,98,\cdots, 0&\color{red}{51}\\ 1&\ \ 95,93,\cdots, 1&\color{blue}{48}\\ 2&\ \ 90,88,\cdots, 0&\color{red}{46}\\ 3&\ \ 85,83,\cdots, 1&\color{blue}{43}\\ 4&\ \ 80,78,\cdots, 0&\color{red}{41}\\ \vdots&\vdots&\vdots\\ 17&15,13,\cdots,1&\color{blue}{8}\\ 18&10,8,\cdots,0&\color{red}{6}\\ 19&5,3,1&\color{blue}{3}\\ 20&0&\color{red}{1}\\ \hline &&\color{red}{286}+\color{blue}{255}=541 \end{array}$$