Kvant Math Problem 238
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m39s
Source on kvant.digital
Problem
Prove that $$C_n^1+C_n^3\cdot1973+C_n^5\cdot1973^2+C_n^7\cdot1973^3+\ldots$$ is divisible by $2^{n-1}$. (Here $C_n^k$ are the coefficients of the polynomial $$(a+b)^n=\textstyle\sum\limits_{k=0}^n C_n^k a^k b^{n-k}.\Big)$$
F. G. Shleifer
Exploration
Let
$$S=C_n^1+C_n^3\cdot1973+C_n^5\cdot1973^2+\cdots.$$
The exponent of $1973$ increases by $1$ whenever the upper index of the binomial coefficient increases by $2$. Thus
$$S=\sum_{m\ge0} C_n^{2m+1}1973^m.$$
The appearance of only odd binomial coefficients suggests separating the odd and even parts of a binomial expansion. Write $1973=x^2$. Then
$$S=\frac1x\sum_{m\ge0}C_n^{2m+1}x^{2m+1}.$$
For any $x$,
$$(1+x)^n-(1-x)^n =2\sum_{m\ge0}C_n^{2m+1}x^{2m+1}.$$
Hence
$$S=\frac{(1+x)^n-(1-x)^n}{2x}.$$
Substituting $x=\sqrt{1973}$ gives
$$S=\frac{(1+\sqrt{1973})^n-(1-\sqrt{1973})^n}{2\sqrt{1973}}.$$
The divisibility by a power of $2$ must come from arithmetic properties of the two algebraic integers
$$a=1+\sqrt{1973},\qquad b=1-\sqrt{1973}.$$
Their sum is $2$ and their product is
$$ab=1-1973=-1972=-2^2\cdot493.$$
Compute a few values of
$$u_n=\frac{a^n-b^n}{a-b}.$$
Since $a-b=2\sqrt{1973}$, we have $S=u_n$.
The numbers $u_n$ satisfy
$$u_{n+2}=(a+b)u_{n+1}-ab,u_n =2u_{n+1}+1972u_n.$$
The first terms are
$$u_1=1,\qquad u_2=2,\qquad u_3=1976.$$
Indeed $u_2$ is divisible by $2$, $u_3$ by $4$, suggesting
$$2^{,n-1}\mid u_n.$$
Define $v_n=u_n/2^{n-1}$. Dividing the recurrence by $2^{n+1}$ yields
$$v_{n+2}=v_{n+1}+493,v_n.$$
Now $v_1=v_2=1$ are integers, and the recurrence has integer coefficients. Hence every $v_n$ is an integer. This immediately gives $2^{n-1}\mid u_n=S$.
The potentially dangerous step is identifying $S$ with $u_n$ and checking the recurrence after dividing by powers of $2$.
Problem Understanding
We are asked to prove that the integer
$$S=\sum_{m\ge0} C_n^{2m+1}1973^m$$
is divisible by $2^{n-1}$ for every positive integer $n$.
This is a Type B problem, a pure proof problem.
The core difficulty is to extract the odd-indexed binomial coefficients in a form that reveals a large power of $2$. The natural tool is the identity obtained from the difference of the binomial expansions of $(1+x)^n$ and $(1-x)^n$.
Proof Architecture
First, express $S$ as
$$S=\frac{(1+\sqrt{1973})^n-(1-\sqrt{1973})^n}{2\sqrt{1973}}.$$
This follows from the standard decomposition of a binomial expansion into its odd-degree part.
Next, define
$$u_n=\frac{a^n-b^n}{a-b}, \qquad a=1+\sqrt{1973},\ b=1-\sqrt{1973},$$
and prove that $S=u_n$.
Then prove that $(u_n)$ satisfies
$$u_{n+2}=2u_{n+1}+1972u_n.$$
This follows from $a+b=2$ and $ab=-1972$.
Define
$$v_n=\frac{u_n}{2^{n-1}}.$$
Show that
$$v_{n+2}=v_{n+1}+493,v_n.$$
This is obtained by dividing the recurrence for $u_n$ by $2^{n+1}$.
Finally, verify that $v_1=v_2=1$ are integers and conclude by induction from the recurrence that every $v_n$ is an integer. Hence $u_n$, and therefore $S$, is divisible by $2^{n-1}$.
The most delicate point is deriving the recurrence for $v_n$ correctly after dividing by powers of $2$.
Solution
Let
$$a=1+\sqrt{1973},\qquad b=1-\sqrt{1973}.$$
Since
$$a-b=2\sqrt{1973},$$
the identity
$$(1+x)^n-(1-x)^n =2\sum_{m\ge0} C_n^{2m+1}x^{2m+1}$$
gives, after substituting $x=\sqrt{1973}$,
$$a^n-b^n =2\sqrt{1973}\sum_{m\ge0} C_n^{2m+1}1973^m.$$
Therefore
$$S=\sum_{m\ge0} C_n^{2m+1}1973^m =\frac{a^n-b^n}{a-b}.$$
Define
$$u_n=\frac{a^n-b^n}{a-b}.$$
Then $u_n=S$.
We compute
$$a+b=2, \qquad ab=(1+\sqrt{1973})(1-\sqrt{1973}) =1-1973 =-1972.$$
Using these relations,
$$\begin{aligned} u_{n+2} &=\frac{a^{n+2}-b^{n+2}}{a-b} \ &=\frac{(a+b)(a^{n+1}-b^{n+1})-ab(a^n-b^n)}{a-b} \ &=(a+b)u_{n+1}-ab,u_n \ &=2u_{n+1}+1972u_n . \end{aligned}$$
Now define
$$v_n=\frac{u_n}{2^{,n-1}}.$$
Since
$$u_n=2^{,n-1}v_n,$$
the recurrence becomes
$$\begin{aligned} 2^{n+1}v_{n+2} &=2\cdot2^n v_{n+1} +1972\cdot2^{n-1}v_n \ &=2^{n+1}v_{n+1} +493\cdot2^{n+1}v_n. \end{aligned}$$
Dividing by $2^{n+1}$ yields
$$v_{n+2}=v_{n+1}+493,v_n.$$
The initial values are
$$u_1=\frac{a-b}{a-b}=1, \qquad u_2=\frac{a^2-b^2}{a-b}=a+b=2,$$
hence
$$v_1=1, \qquad v_2=1.$$
The recurrence
$$v_{n+2}=v_{n+1}+493,v_n$$
has integer coefficients, and $v_1,v_2$ are integers. By induction on $n$, every $v_n$ is an integer.
Consequently,
$$u_n=2^{,n-1}v_n$$
is divisible by $2^{n-1}$ for every $n$.
Since $u_n=S$, we obtain
$$2^{,n-1}\mid \left( C_n^1+C_n^3\cdot1973+C_n^5\cdot1973^2+\cdots \right).$$
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the transformation of the sum into a binomial difference. Expanding both $(1+x)^n$ and $(1-x)^n$ gives
$$(1+x)^n-(1-x)^n = \sum_{k=0}^n C_n^k\bigl(1-(-1)^k\bigr)x^k.$$
For even $k$ the coefficient is $0$, and for odd $k$ it is $2$. Hence
$$(1+x)^n-(1-x)^n = 2\sum_{m\ge0}C_n^{2m+1}x^{2m+1},$$
which justifies the identification
$$S=\frac{a^n-b^n}{a-b}.$$
The second delicate step is the recurrence for $u_n$. Starting from
$$a^{n+2}-b^{n+2} =(a+b)(a^{n+1}-b^{n+1})-ab(a^n-b^n),$$
one checks by expansion that the mixed terms cancel:
$$(a+b)(a^{n+1}-b^{n+1}) -ab(a^n-b^n) = a^{n+2}-b^{n+2}.$$
Substituting $a+b=2$ and $ab=-1972$ gives exactly
$$u_{n+2}=2u_{n+1}+1972u_n.$$
The third delicate step is dividing by powers of $2$. Since
$$1972=4\cdot493,$$
the term
$$1972\cdot2^{n-1} = 493\cdot2^{n+1},$$
which is why the recurrence for $v_n$ contains the integer coefficient $493$. Missing this factor of $4$ would produce an incorrect recurrence and invalidate the divisibility argument.
Alternative Approaches
One may work directly with the sequence $u_n=(a^n-b^n)/(a-b)$ and prove by induction that
$$u_n=2^{n-1}w_n$$
for some integer $w_n$. Using the recurrence
$$u_{n+2}=2u_{n+1}+1972u_n,$$
the inductive step becomes
$$u_{n+2} = 2^n w_{n+1} + 493\cdot2^{n+1}w_n = 2^{n+1}(w_{n+1}+493w_n).$$
This yields the desired divisibility without introducing the normalized sequence $v_n$ explicitly.
Another approach uses algebraic integers. Since
$$a+b=2,\qquad ab=-4\cdot493,$$
one shows inductively that
$$\frac{a^n-b^n}{a-b} = 2^{n-1}\cdot(\text{integer}),$$
because every symmetric polynomial in $a$ and $b$ can be expressed as an integer polynomial in $a+b$ and $ab$. The recurrence method is preferable because it isolates the power of $2$ immediately and keeps all computations elementary.