Kvant Math Problem 602
Let the three consecutive entries in row $n$ be
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m50s
Source on kvant.digital
Problem
Fig. 1. In the $n$th row, the $k$th number is equal to $C_n^k=\dfrac{n(n-1)\ldots(n-k+1)}{1\cdot2\cdot\ldots\cdot k}$
In Pascal’s triangle, whose beginning is shown in Fig. 1 (each “interior” number is equal to the sum of the two numbers above it), the seventh row contains three consecutive numbers that form an arithmetic progression.
- In which subsequent row will the same phenomenon occur?
- Prove that it occurs in infinitely many rows, and try to determine all the row numbers for which this happens.
A. Avramov
Exploration
Let the three consecutive entries in row $n$ be
$$\binom{n}{k-1},\qquad \binom{n}{k},\qquad \binom{n}{k+1}.$$
They form an arithmetic progression if and only if
$$2\binom{n}{k}=\binom{n}{k-1}+\binom{n}{k+1}.$$
Using
$$\binom{n}{k-1}=\binom{n}{k}\frac{k}{n-k+1}, \qquad \binom{n}{k+1}=\binom{n}{k}\frac{n-k}{k+1},$$
the condition becomes
$$2=\frac{k}{n-k+1}+\frac{n-k}{k+1}.$$
Multiplying by $(n-k+1)(k+1)$ gives
$$2(n-k+1)(k+1)=k(k+1)+(n-k)(n-k+1).$$
Writing $a=k$ and $b=n-k$, this is
$$2(a+1)(b+1)=a(a+1)+b(b+1).$$
Expanding,
$$a^2+b^2-2ab-a-b-2=0,$$
hence
$$(a-b)^2-(a+b)-2=0.$$
Since $a+b=n$,
$$(2k-n)^2=n+2.$$
This is the decisive simplification. The existence of three consecutive binomial coefficients in arithmetic progression in row $n$ is equivalent to the Diophantine condition
$$n+2=t^2,$$
where $t=|2k-n|$.
Testing small values,
$$n=7 \implies n+2=9=3^2,$$
which is the example from the statement.
The next value is
$$n+2=16,$$
so $n=14$.
For every square $t^2\ge 9$,
$$n=t^2-2$$
works. We must also check that a corresponding integer $k$ exists. From
$$|2k-n|=t,$$
we obtain
$$k=\frac{n\pm t}{2}.$$
Substituting $n=t^2-2$,
$$k=\frac{t^2\pm t-2}{2}.$$
If $t$ is odd, then $t^2-2$ is odd and $n\pm t$ is even. If $t$ is even, then $t^2-2\equiv 2\pmod 2$ and again $n\pm t$ is even. Thus $k$ is always integral. Moreover,
$$0\le \frac{n-t}{2} =\frac{t^2-t-2}{2},$$
for $t\ge 2$, so the corresponding entries indeed lie in the row.
Hence the rows are exactly
$$n=t^2-2,\qquad t\ge 3.$$
The step most likely to conceal an error is the derivation of
$$(2k-n)^2=n+2,$$
because any algebraic mistake there would completely change the classification.
Problem Understanding
We seek all rows of Pascal's triangle that contain three consecutive entries forming an arithmetic progression.
If the consecutive entries are
$$\binom{n}{k-1},\ \binom{n}{k},\ \binom{n}{k+1},$$
then we must determine for which row numbers $n$ there exists an index $k$ such that
$$2\binom{n}{k} = \binom{n}{k-1} + \binom{n}{k+1}.$$
This is a Type A problem. We must classify all row numbers $n$ for which such a triple exists, prove that every listed row works, and prove that no other row works.
The core difficulty is converting the condition on three binomial coefficients into a tractable Diophantine equation.
The answer will be that the phenomenon occurs exactly in the rows
$$n=t^2-2,\qquad t=3,4,5,\ldots$$
The first row after $n=7$ is therefore $n=14$.
Proof Architecture
Lemma 1. Three consecutive entries $\binom{n}{k-1},\binom{n}{k},\binom{n}{k+1}$ form an arithmetic progression if and only if
$$(2k-n)^2=n+2.$$
This follows by expressing the neighboring binomial coefficients through $\binom{n}{k}$ and simplifying.
Lemma 2. If a row $n$ contains such a progression, then $n+2$ is a perfect square.
This is immediate from Lemma 1.
Lemma 3. If $n=t^2-2$ with $t\ge3$, then row $n$ contains such a progression.
Choosing
$$k=\frac{n+t}{2}$$
or
$$k=\frac{n-t}{2}$$
gives $(2k-n)^2=t^2=n+2$, and Lemma 1 applies.
The hardest direction is proving necessity, namely that every admissible row number must satisfy $n+2=t^2$.
The lemma most likely to fail under scrutiny is Lemma 1, since it contains all the essential algebra.
Solution
Let
$$\binom{n}{k-1},\qquad \binom{n}{k},\qquad \binom{n}{k+1}$$
be three consecutive entries of the $n$th row of Pascal's triangle.
They form an arithmetic progression precisely when
$$2\binom{n}{k} = \binom{n}{k-1} + \binom{n}{k+1}.$$
Using the standard relations
$$\binom{n}{k-1} = \binom{n}{k}\frac{k}{n-k+1}, \qquad \binom{n}{k+1} = \binom{n}{k}\frac{n-k}{k+1},$$
and dividing by the positive number $\binom{n}{k}$, we obtain
$$2 = \frac{k}{n-k+1} + \frac{n-k}{k+1}.$$
Multiplying by $(n-k+1)(k+1)$ yields
$$2(n-k+1)(k+1) = k(k+1)+(n-k)(n-k+1).$$
Set
$$a=k,\qquad b=n-k.$$
Then $a+b=n$, and the equation becomes
$$2(a+1)(b+1) = a(a+1)+b(b+1).$$
Expanding and simplifying,
$$a^2+b^2-2ab-a-b-2=0.$$
Since
$$a^2+b^2-2ab=(a-b)^2$$
and
$$a+b=n,$$
we obtain
$$(a-b)^2=n+2.$$
Because
$$a-b=k-(n-k)=2k-n,$$
the condition is equivalent to
$$(2k-n)^2=n+2. \tag{1}$$
This proves Lemma 1.
Suppose now that the row $n$ contains three consecutive entries in arithmetic progression. Then equation (1) holds for some integer $k$. Hence $n+2$ is the square of the integer $2k-n$. Therefore
$$n=t^2-2$$
for some integer $t\ge3$.
This proves necessity.
Conversely, let
$$n=t^2-2, \qquad t\ge3.$$
Define
$$k=\frac{n+t}{2}.$$
Since $n=t^2-2$, the numbers $n$ and $t$ have the same parity, so $k$ is an integer.
Furthermore,
$$0\le \frac{n-t}{2} = \frac{t^2-t-2}{2},$$
because $t\ge3$. Hence
$$t\le n,$$
and therefore
$$0\le k\le n.$$
Now
$$2k-n=t,$$
so
$$(2k-n)^2=t^2=n+2.$$
By Lemma 1, the three consecutive entries
$$\binom{n}{k-1},\qquad \binom{n}{k},\qquad \binom{n}{k+1}$$
form an arithmetic progression.
Thus every row of the form
$$n=t^2-2,\qquad t\ge3,$$
has the required property.
We have proved both directions. Hence the row numbers are exactly
$$n=t^2-2,\qquad t=3,4,5,\ldots$$
The first given example corresponds to
$$7=3^2-2.$$
The next one is
$$14=4^2-2.$$
Therefore the next row after the seventh is the fourteenth row, and all such rows are precisely those whose number is two less than a perfect square.
$$\boxed{{,t^2-2\mid t=3,4,5,\ldots,}}$$
Verification of Key Steps
The crucial algebra begins with
$$2=\frac{k}{n-k+1}+\frac{n-k}{k+1}.$$
Multiplying out gives
$$2(n-k+1)(k+1) = k(k+1)+(n-k)(n-k+1).$$
Introducing $a=k$ and $b=n-k$ reduces this to
$$2(a+1)(b+1)=a(a+1)+b(b+1).$$
Expanding both sides produces
$$2ab+2a+2b+2=a^2+a+b^2+b,$$
hence
$$(a-b)^2=a+b+2=n+2.$$
No cancellation has been omitted.
For sufficiency, take $n=t^2-2$ and
$$k=\frac{n+t}{2}.$$
Parity must be checked. If $t$ is even, then $n=t^2-2$ is even. If $t$ is odd, then $n$ is odd. In both cases $n+t$ is even, so $k$ is integral.
The boundary condition $k\le n$ requires
$$\frac{n+t}{2}\le n,$$
equivalent to $t\le n$. Since
$$n-t=t^2-t-2=(t-2)(t+1)\ge0$$
for $t\ge3$, the chosen index indeed belongs to the row.
Alternative Approaches
Instead of introducing $a=k$ and $b=n-k$, one may start from
$$2=\frac{k}{n-k+1}+\frac{n-k}{k+1}$$
and clear denominators directly. After expansion and simplification, the resulting quadratic equation in $k$ becomes
$$4k^2-4nk+n^2-n-2=0,$$
which can be rewritten as
$$(2k-n)^2=n+2.$$
The remainder of the argument is unchanged.
A generating-function approach is also possible. Since consecutive binomial coefficients satisfy simple ratio relations, the arithmetic-progression condition can be translated into a rational equation involving the quotient
$$\frac{\binom{n}{k+1}}{\binom{n}{k}}.$$
That route again reduces to the same quadratic relation. The direct algebraic derivation above is preferable because it reaches the Diophantine condition in a few elementary steps and immediately yields the complete classification.