In multiple choice test had a problem: How many positive integer solutions of $z_2+z_3+z_4+z_5=n$ satisfing $i\not\mid z_i$
Answer:
A. $\displaystyle\sum_{k=2}^n \left\lfloor\dfrac{{k\choose 2}}{5}\right\rfloor$
B. $\left\lfloor\dfrac{(n-1)(n-2)(n+3)}{30}\right\rfloor$
———
My solution:
We have general function $$\begin {align*} G(x)&=\left(\dfrac{1}{1-x}-(1+x^2+x^4+…)\right) \left(\dfrac{1}{1-x}-(1+x^3+x^6+…)\right)\\ &\quad \left(\dfrac{1}{1-x}-(1+x^4+x^8+…)\right) \left(\dfrac{1}{1-x}-(1+x^5+x^{10}+…)\right)\\ &= \frac {x^4}{(1-x)^4(1+x+x^2+x^3+x^4)} \end{align*}$$ $$\begin {align*} G(x)&=\frac { x^4}{(x-1)^4(1+x+x^2+x^3+x^4)}\\ &=\frac{x+x^2-x^3-x^4}{5(1-x^5)}+\frac{1}{5(1-x)}\\ &\quad -\frac{2}{5(1-x)^3}+\frac{1}{5(1-x)^4}\\ \Longrightarrow \left [ x^n \right ]G(x)&=\left ( \left [x^{n-1} \right ]+\left [x^{n-2} \right ]-\left [x^{n-3} \right ]-\left [x^{n-4} \right ] \right )\frac {1}{5}\sum_{k\geq 0}x^{5k}\\ &\quad +\frac {1}{5}-\frac {2}{5}\binom{n+2}{2}+\frac {1}{5}\binom{n+3}{3} \end {align*} $$
Number of solutions : $$\left [ x^n \right ]G(x)= \left \{ \begin{matrix} & \frac {1}{5}-\frac {2}{5}\binom{n+2}{2}+\frac {1}{5}\binom{n+3}{3} &&\text{if $n \equiv 0\!\! \pmod{5}$ }\\ & \frac {2}{5}-\frac {2}{5}\binom{n+2}{2}+\frac {1}{5}\binom{n+3}{3}&&\text{if $n \equiv 1,2\!\! \pmod{5}$ } \\ &-\frac {2}{5}\binom{n+2}{2}+\frac {1}{5}\binom{n+3}{3} &&\text{if $n \equiv 3,4\!\! \pmod{5}$ } \end{matrix}\right.$$ My choice B. answer but answer exacted is A. WHY?
You've already got $$[x^n]G(x)=\sum_{m=1}^{\lfloor\frac{n+1}{5}\rfloor}\binom{n-5m+3}{2}$$
This answer proves the following two claims :
Claim 1 : $$\sum_{m=1}^{\lfloor\frac{n+1}{5}\rfloor}\binom{n-5m+3}{2}=\sum_{k=2}^{n}\left\lfloor\frac{\binom k2}{5}\right\rfloor$$
Claim 2 : $$\sum_{m=1}^{\lfloor\frac{n+1}{5}\rfloor}\binom{n-5m+3}{2}=\left\lfloor\frac{(n-1)(n-2)(n+3)}{30}\right\rfloor$$
Claim 1 : $$\sum_{m=1}^{\lfloor\frac{n+1}{5}\rfloor}\binom{n-5m+3}{2}=\sum_{k=2}^{n}\left\lfloor\frac{\binom k2}{5}\right\rfloor$$
Proof :
Let $k:=n-5m+3$. Then, $$\sum_{m=1}^{\lfloor\frac{n+1}{5}\rfloor}\binom{n-5m+3}{2}=\sum_{k\in\{n-5\lfloor\frac{n+1}{5}\rfloor+3,n-5\lfloor\frac{n+1}{5}\rfloor+8,\cdots, n-2\}}\binom k2 =\sum_{k\in\{n-2-5(\lfloor\frac{n+1}{5}\rfloor-1),n-2-5(\lfloor\frac{n+1}{5}\rfloor-2),\cdots, n-2\}}\binom k2\tag1$$
For any integer $s$, we have $$\binom{n-2-5s}2=\left\lfloor\frac 15\binom{n-5s}{2}\right\rfloor+\left\lfloor\frac 15\binom{n-1-5s}{2}\right\rfloor+\left\lfloor\frac 15\binom{n-2-5s}{2}\right\rfloor+\left\lfloor\frac 15\binom{n-3-5s}{2}\right\rfloor+\left\lfloor\frac 15\binom{n-4-5s}{2}\right\rfloor\tag2$$
A proof of $(2)$ is as follows :
Let $n=5t+r$ where $t\in\mathbb Z$ and $r=0,1,2,3,4$.
Then, the RHS of $(2)$ can be written as $$-5s(5t+r)+\frac{25s(s+1)}{2}+5tr+\frac{25t(t-1)}{2}+F(r)$$ where $$F(r)=\left\lfloor \frac{r(r-1)}{10}\right\rfloor +\left\lfloor \frac{(r-2)(r-1)}{10}\right\rfloor+\left\lfloor\frac{(r-2)(r-3)}{10}\right\rfloor+\left\lfloor\frac{(r-3)(r-4)}{10}\right\rfloor+\left\lfloor\frac{(r-4)(r-5)}{10}\right\rfloor$$
So, $(2)$ is equivalent to $$\frac{(r-2)(r-3)}{2}=F(r)\tag3$$ Considering $r=0,1,2,3$ and $4$, we can see that $(3)$ holds. So, $(2)$ holds.
Therefore, from $(2)$, we get $$(1)=\sum_{k=n-4-5(\lfloor\frac{n+1}{5}\rfloor-1)}^{n}\left\lfloor\frac{\binom k2}{5}\right\rfloor=\sum_{k=2}^{n}\left\lfloor\frac{\binom k2}{5}\right\rfloor.\blacksquare$$
Claim 2 : $$\sum_{m=1}^{\lfloor\frac{n+1}{5}\rfloor}\binom{n-5m+3}{2}=\left\lfloor\frac{(n-1)(n-2)(n+3)}{30}\right\rfloor$$
Proof :
Let $n=5t+r$ where $t\in\mathbb Z$ and $r=0,1,2,3,4$.
For $0\le r\le 3$, we have $$\frac{(n-1)(n-2)(n+3)}{30}=t(4t^2+2rt-1)+\underbrace{\frac{tr(t+r)}{2}}_{\text{integer}} + \underbrace{\frac{(t-1)t(t+1)}{6}}_{\text{integer}} +\underbrace{\frac{(r - 1) (r - 2) (r + 3)}{30}}_{\lt 1}$$ Since $\lfloor\frac{n+1}{5}\rfloor=t$, we get $$\text{RHS}-\text{LHS}=t(4t^2+2rt-1)+\frac{tr(t+r)}{2} + \frac{(t-1)t(t+1)}{6} -\frac 16 t (3 r^2 + 15 r t + 25 t^2 - 7)=0$$
For $r=4$, we have $$\frac{(n-1)(n-2)(n+3)}{30}=4t^3+10t^2+7t+1+\underbrace{\frac{(t-1)t(t+1)}{6}}_{\text{integer}}+\frac 25 $$ Since $\lfloor\frac{n+1}{5}\rfloor=t+1$, we get $$\text{RHS}-\text{LHS}=4t^3+10t^2+7t+1+\frac{(t-1)t(t+1)}{6}-\frac 16 (25 t^3 + 60 t^2 + 41 t + 6)=0$$
Therefore, claim 2 follows.$\ \blacksquare$