2

Define $P(n)$ to be the number of solutions : $a,\ b,\ c,\ d$ are nonnegative integers s.t.

$$a+b+c+d=n $$ and $$ a\geq b,\ d,\ {\rm and}\ c\geq b+1,\ d$$

Define $Q(n)$ to be the number of solutions : $x,\ y,\ z,\ w $ are nonnegative integers s.t.

$$ x+y+2z+3w= n-1 $$

Prove that $P(n)= Q(n)$ for all $n$

Proof : First we consider the case where $b=z,\ d=w$. I think that this is the easiest case. (Surely we can use the other case. For instance, $b={\rm max}\ \{w,z\} - {\rm min}\ \{ w,z\}$.)

If we set

$$a = x+{\rm max}\ \{w,z\},\ b=z,\ d=w,\ c=y+{\rm max}\ \{w,z+1\} $$

then we have the condition $$a\geq b,\ d\ {\rm and}\ c\geq b+1,\ d$$

If $w\geq z+1$, then $$ a+b+c+d = x+w+z+w+y+w =n-1-z$$

How can we prove this ?

HK Lee
  • 19,964
  • You have the right idea (of creating bijection via relationship between the variables), but just need to find one that works. EG Setting $ a = x+w+z, d = z$ results in $a \geq d + $stuff, which isn't a given condition, so why try that? – Calvin Lin Aug 21 '21 at 15:56
  • I also think that this approach is correct. I show randomly one example in the posting. I can not find a suitable $bijection$ and I suspect that there is a typo in this problem. – HK Lee Aug 21 '21 at 22:59
  • Note: I might have misread the condition. To clarify, it should be $ a\geq \max(b, d), c \geq \max (b+1, d ) $? – Calvin Lin Aug 22 '21 at 01:40
  • Yes. That is the condition. – HK Lee Aug 22 '21 at 01:48
  • If $\sum_i C_i x^i = \sum_i x^i\cdot\sum_i x^{2i}\cdot\sum_i x^{3i}$, then $Q(n)=C_{n-1} +C_{n-2}+\cdots +C_0$ (which is well-known). – HK Lee Aug 22 '21 at 02:02

1 Answers1

2

Let \begin{align*} P_n &= \{(a, b, c, d) \in \mathbb{N}_0^4 : a + b + c + d = n, a \geq b, d, c \geq b + 1, d\}\\ Q_n &=\{(x, y, z, w) \in \mathbb{N}_0^4 : x + y + 2z + 3w = n - 1\} \end{align*} so $|P_n| = P(n)$ and $|Q_n| = Q(n)$.

We will proceed by induction to show $P(n) = Q(n)$ for all $n \geq 0$.

Note that the base cases are true since $P(0) = Q(0) = 0$ and $P(1) = Q(1) = 1$.

Now suppose true for $n$. Then for $n + 1$, we will show that $P(n+1) - P(n) = Q(n+1) - Q(n)$:

Note that if $(x, y, z, w) \in Q_n$, then $(x + 1, y, z, w) \in Q_{n+1}$ and for all $(x, y, z, w) \in Q_{n+1}$ such that $x \neq 0$, $(x - 1, y, z, w) \in Q_n$. Hence, $Q(n+1) - Q(n)$ represents the number of non-negative integer solutions to $y + 2z + 3w = n$.

Also note that if $(a, b, c, d) \in P_n$, then $(a + 1, b, c, d) \in P_{n+1}$ and for all $(a, b, c, d) \in P_{n+1}$ such that $a > \max(b, d)$, $(a - 1, b, c, d) \in P_n$. Hence, $P(n+1) - P(n)$ represents the number of non-negative integer solutions to $\max(b, d) + b + c + d = n + 1$ with $c \geq b + 1, d$.

In the case where $b \geq d$, we have $b = d + k$, $c = d + k + l + 1$ with $k, l \geq 0$, so $l + 3k + 4d = n$. Hence, this case counts the number of solutions to $y + 2z + 3w = n$ where $z$ is even ($z = 2d$).

In the case where $d > b$, we have $d = b + k + 1$, $c = b + k + l + 1$ with $k, l \geq 0$, so $l + 3k + 4b = n - 2$. Hence, this case counts the number of solutions to $y + 2z + 3w = n$ where $z$ is odd ($z = 2b + 1$).

But these two cases count the total number of solutions so we get that $Q(n+1) - Q(n) = P(n+1) - P(n)$.

Since $P(n) = Q(n)$, we get that $P(n+1) = Q(n+1)$.

Therefore, by induction we're done.

Note that this also yields the following bijection from $Q_n \to P_n$: \begin{align*} (x, y, z, w) \mapsto \begin{cases} \left ( x + \frac{z}{2} + w, \frac{z}{2} + w, y + \frac{z}{2} + w + 1, \frac{z}{2}\right ) & \text{if $z$ is even}\\ \left ( x + \frac{z + 1}{2} + w, \frac{z - 1}{2}, y + \frac{z + 1}{2} + w, \frac{z + 1}{2} + w\right ) & \text{if $z$ is odd} \end{cases} \end{align*}

Sharky Kesa
  • 4,137