On existence of positive integer solution of $\binom{x+y}{2}=ax+by$

Question

How can I prove this?

Prove that for any two positive integers $a,b$ there are two positive integers $x,y$ satisfying the following equation: $$\binom{x+y}{2}=ax+by$$

My idea was that $\binom{x+y}{2}=\dfrac{x+2y-1}{2}+\dfrac{y(y-1)}{2}$ and choose $x,y$, such that $2a=x+2y-1, 2b=y(y-1)$, but using this idea, $x,y$ won’t be always positive.

Answer 1

Case 1: $a=b$.

$${x+y \choose 2}=ax+ay$$

$$\frac{(x+y)(x+y-1)}{2}=a(x+y)$$

$$x+y-1=2a$$

$$x+y=2a+1$$

Basically, you can set $y=1$ and this gives $x=2a$.

Case 2: $a\gt b$

Introduce substitution:

$$x=u+v\tag{1}$$

$$y=u-v\tag{2}$$

So the equation:

$${x+y \choose 2}=ax+by$$

...now becomes:

$${2u \choose 2}=\frac{2u(2u-1)}{2}=a(u+v)+b(u-v)$$

You can now express v as a function of u:

$$v=\frac{u(2u-a-b-1)}{a-b}\tag{3}$$

Now replace (3) into (1) and (2) and the result is:

$$x={u(2u-2b-1) \over a-b}\tag{4}$$

$$y={u(2a+1-2u) \over a-b}\tag{5}$$

From (4), using condition that $x>0$ we have:

$$u>b+\frac12\tag{6}$$

From (5), usgin condition that $y>0$ we get:

$$u < a + \frac 12\tag{7}$$

If we limit the choice of parameter $u$ to natural numbers we have:

$$b+1\le u \le a\tag{8}$$

Is it possible to choose the value for $u$ so that expressions (4) and (5) produce positive integer values? Actually, it is! Available values for $u$ are in the set of $a-b$ consecutive integer numbers, from $b$ (exclusive) to $a$ (inclusive). Obviously, one of those numbers must be divisible by $a-b$. That value of $u$ will cancel the denominator in (4) and (5) thus generating integer values for $x$ and $y$!

Example: $a=5, b=2$. We have to pick the value for $u$ that is greater than 2, less or equal to 5 and divisible by 5-2=3. The only possible choice is $u=3$. From (4) and (5) we get: $x=1,y=5$. One can easily check that ${1+5 \choose 2}=5\times 1+2\times 5$.

Case 3: $a\lt b$

This is not a new case at all. You can always convert this type of problem into the following form:

$${y+x \choose 2}=by+ax$$

Now replace $x$ with $y$ and $y$ with $x$ and you'll get the case (2) that we already considered.

BTW, excellent problem, it's too bad that it did not get enough attention.

Answer 2

Because of simmetry we can assume WLOG that $a\geq b$

• If $a>b$:

Let $m=2a+1$ and $n=2b+1$ and $k= m-n$. Since $k$ is even $k$ does not divide odd numbers $m$ and $n$. Since $${m\over k}-{n\over k} = {m-n\over m-n} = 1$$ we see exists natural number $p$ in $\displaystyle\Big({n\over k},{m\over k}\Big)$. Now let $$x=p(pk-n)$$ and $$y=p(m-pk)$$ We can easly see that $x,y$ are good and we are done.

• If $a=b$ then let $z=x+y$ and we have $z(z-1)=2az $ so $z=2a+1$. Clearly then $x=a+1$ and $y=a$ works.

Answer 3

Consider the equation $f(x,y)=x^2+2xy+y^2-(2a+1)x-(2b+1)y=0$. If $a=b$ then this is satisfied along the parallel lines $x+y=0$ and $x=y+2a+1$, so we can choose say $x=1$, $y=2a$.

From now on we assume $a>b$. Then the equation is satisfied along a parabola, passing through points $O=(0,0)$, $A=(2a+1,0)$ and $B=(0,2b+1)$ and having its vertex in the second quarter plane.

Starting from the origin, we can perform a sequence of Viéte jumps: $$ (x,y) \mapsto \big(x,2b+1-2x-y\big) \mapsto \big(2a+1-2(2b+1-2x-y)-x,2b+1-2x-y\big) \mapsto \ldots $$ All these lattice points lie on the parabola. We continue this sequence until we get onto the arc $AB$.

More formally, let $P_n=(x_n,y_n)$ with $$ x_0=y_0=0, \quad x_{n+1}=2a-4b-1+3x_n+2y_n, \quad y_{n+1}=2b+1-2x_n-y_n. $$ Notice that $x_{n+1}+y_{n+1}=x_n+y_n+2(a-b)$, so $x_n+y_n=2(a-b)n$. Hence, we must take the unique index $n$ with $2b+1<2(a-b)n<2a+1$ in order to find $P_n$ inside arc $AB$. Solving the equations $f(x,y)=0$, $x+y=2(a-b)n$, the coordinates are $$ x_n = \big(2(a-b)n-(2b+1)\big)n, \quad y_n = \big((2a+1)-2(a-b)n\big)n. $$

(The picture shows the case $a=8$, $b=6$.)

Answer 4

If $a=b$ then let $(x,y)=(a,a+1)$.

Otherwise, w.l.g. suppose $a>b$ and let $x+y=2t(a-b)$ for some positive integer $t$. Then $$t(a-b)\Big(2t(a-b)-1\Big) =ax+by=(a-b)x+2bt(a-b)$$ $\text{Therefore } x=t\Big(2t(a-b)-1\Big)-2bt=t\Big(2t(a-b)-(2b+1)\Big)$.

$x$ will be a positive integer providing $t>\frac{2b+1}{2(a-b)}.$

$y=2t(a-b)-x$ will be a positive integer providing $2(a-b)>2t(a-b)-(2b+1)$ i.e. $\frac{2b+1}{2(a-b)}>t-1$.

$\frac{2b+1}{2(a-b)}$ is positive but not an integer and so, precisely as required, there is a positive integer $t$ such that $$t>\frac{2b+1}{2(a-b)}>t-1.$$

Answer 5

Case $a=b$ is trivial after dividing both sides by $x+y$, $a$ and $b$ are symmetric in the problem, so in the following text WLOG I assume $a < b$.

One can visualize the problem as follows. Denote $z=x+y$, then the left-hand side is $\frac{z(z-1)}{2}$. Let's subdivide the interval $(az, bz)$ into $z$ equal parts: then the right-hand side can be any point of subdivision (not including the ends) if you choose appropriate $x$ and $y$. So the problem is equivalent to finding $z$ such that $\frac{z(z-1)}{2}$ is a point of the subdivision of interval $(az, bz)$ into $z$ equal parts. If we multiply everything ($\frac{z(z-1)}{2}$, interval ends and points of the subdivision) in this condition by $2/z$, it becomes:

Condition. $(z-1)$ is a point of the subdivision of interval $(2a, 2b)$ into $z$ equal parts.

Now the simplest try of finding such $z$ seems to be: make all integer points between $2a$ and $2b$ the points of subdivision into $z$ equal parts, while $2a < z-1 < 2b$, making $z-1$ a point of such subdivision, because it is an integer. All integer points on $(2a, 2b)$ are in subdivision into $z$ equal parts iff $z$ is a multiple of $d=2b-2a$. Let's consider as possible values $(z-1)=-1,(-1+d),(-1+2d),(-1+3d),\cdots$ This is a progression with step $d$ which will definitely hit the segment $[2a, 2b]$ of length $d$, and because all its members are odd, it will actually hit the interval $(2a, 2b)$. The $z$ for which this happens satisfies both $2a < z-1 < 2b$ and $d \mid z$ conditions, as required.