Maths Olympiad Prep

Track / Stage 8 / 52 of 180 #1752 of 1964

Problem 1752

IMO Shortlist mid-range; USAMO P2/P5
Algebra Difficulty 8.2 Prove it

3.92 {xnnN}\left\{x_{n} \mid n \in N\right\} is a sequence of real numbers, and for each positive integer n2n \geqslant 2, we have
x1Cn1x2+Cn2x3+(1)nCnnxn+1=0x_{1}-C_{n}^{1} x_{2}+C_{n}^{2} x_{3}-\cdots+(-1)^{n} C_{n}^{n} x_{n+1}=0

Prove that for each positive integer k,n,1kn1k, n, 1 \leqslant k \leqslant n-1, we have
p=0n(1)pCnpxp+1k=0.\sum_{p=0}^{n}(-1)^{p} C_{n}^{p} \cdot x_{p+1}^{k}=0 .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

[Proof] Take the arithmetic sequence {annN}\left\{a_{n} \mid n \in N\right\}, where
a1=x1,a2=x2a_{1}=x_{1}, a_{2}=x_{2}, and the common difference d=x2x1d=x_{2}-x_{1}.

Notice that
p=0n(1)pCnpap+1=p=0n(1)pCnp(a1+pd)=a1p=0n(1)pCnp+dp=0n(1)ppCnp\begin{aligned} \sum_{p=0}^{n}(-1)^{p} C_{n}^{p} a_{p+1} & =\sum_{p=0}^{n}(-1)^{p} C_{n}^{p}\left(a_{1}+p d\right) \\ & =a_{1} \sum_{p=0}^{n}(-1)^{p} C_{n}^{p}+d \sum_{p=0}^{n}(-1)^{p} p C_{n}^{p} \end{aligned}

And
pCnp=pn!p!(np)!=n(n1)!(p1)!(np)!=nCn1p1,p C_{n}^{p}=p \cdot \frac{n!}{p!(n-p)!}=\frac{n \cdot(n-1)!}{(p-1)!(n-p)!}=n C_{n-1}^{p-1},
0=(11)n=p=0n(1)pCnp,0=(11)n1=q=0n1(1)qCn1q=p=0n(1)p1Cn1p1, (let q=p1 ) \begin{array}{l} 0=(1-1)^{n}=\sum_{p=0}^{n}(-1)^{p} C_{n}^{p}, \\ 0=(1-1)^{n-1}=\sum_{q=0}^{n-1}(-1)^{q} C_{n-1}^{q}=\sum_{p=0}^{n}(-1)^{p-1} C_{n-1}^{p-1}, \\ \text { (let } q=p-1 \text { ) } \end{array}

We have
p=0n(1)pCnpan+1=dp=1n(1)pnCn1p1=dnp=1n(1)p1Cn1p1=0\begin{aligned} \sum_{p=0}^{n}(-1)^{p} C_{n}^{p} a_{n+1} & =d \sum_{p=1}^{n}(-1)^{p} n C_{n-1}^{p-1} \\ & =-d n \sum_{p=1}^{n}(-1)^{p-1} C_{n-1}^{p-1}=0 \end{aligned}

Given x1=a1,x2=a2x_{1}=a_{1}, x_{2}=a_{2}.
Assume that we have proved x1=a1,x2=a2,,xk=akx_{1}=a_{1}, x_{2}=a_{2}, \cdots, x_{k}=a_{k}, where kk is some number not less than 2.

In the given equation, let n=kn=k, we get
x1Ck1x2+Ck2x3+(1)k1Ckk1xk+(1)kCkkxk+1=0,x_{1}-C_{k}^{1} x_{2}+C_{k}^{2} x_{3}-\cdots+(-1)^{k-1} C_{k}^{k-1} x_{k}+(-1)^{k} C_{k}^{k} x_{k+1}=0,

In the equation we have proved
p=0n(1)ρCnρan+1=0\sum_{p=0}^{n}(-1)^{\rho} C_{n}^{\rho} a_{n+1}=0

let n=kn=k, we get
a1Ck1a2+Ck2a3+(1)k1Ckk1ak+(1)kCkkak+1=0,a_{1}-C_{k}^{1} a_{2}+C_{k}^{2} a_{3}-\cdots+(-1)^{k-1} C_{k}^{k-1} a_{k}+(-1)^{k} C_{k}^{k} a_{k+1}=0,
(1) - (2), and by the induction hypothesis, we get
(1)kCkk(xk+1ak+1)=0(-1)^{k} C_{k}^{k}\left(x_{k+1}-a_{k+1}\right)=0

Thus, xk+1=ak+1x_{k+1}=a_{k+1}.
By the principle of mathematical induction, xn=an,nNx_{n}=a_{n}, n \in N.
In other words, the sequence {xnnN}\left\{x_{n} \mid n \in N\right\} given in the problem is an arithmetic sequence.
Next, we prove a strengthened proposition: If {xnnN}\left\{x_{n} \mid n \in N\right\} is an arithmetic sequence, then
p=0n(1)pCnpxp+1k=0\sum_{p=0}^{n}(-1)^{p} C_{n}^{p} x_{p+1}^{k}=0

where kN,nk+1k \in N, n \geqslant k+1.
Clearly, from the above discussion, the strengthened proposition holds for k=1k=1 for all nk+1n \geqslant k+1.

Assume that for some positive integer kk, we have already proved
p=0n(1)pCmpxp+1k=0\sum_{p=0}^{n}(-1)^{p} C_{m}^{p} x_{p+1}^{k}=0

for all nk+1n \geqslant k+1.
Then, for n(k+1)+1n \geqslant(k+1)+1, we have
p=0n(1)pCnpxp+1k+1=p=0n(1)pCnpxp+1kxp+1=p=0n(1)pCnpxp+1k(x1+pd)=x1p=0n(1)pCnpxp+1k+dp=0n(1)ppCnpxp+1k=ndp=1n(1)pCn1p1xp+1k=ndq=0n1(1)qCn1pyq+1k.\begin{aligned} & \sum_{p=0}^{n}(-1)^{p} C_{n}^{p} x_{p+1}^{k+1}=\sum_{p=0}^{n}(-1)^{p} C_{n}^{p} \cdot x_{p+1}^{k} \cdot x_{p+1} \\ = & \sum_{p=0}^{n}(-1)^{p} C_{n}^{p} x_{p+1}^{k} \cdot\left(x_{1}+p d\right) \\ = & x_{1} \sum_{p=0}^{n}(-1)^{p} C_{n}^{p} x_{p+1}^{k}+d \sum_{p=0}^{n}(-1)^{p} \cdot p \cdot C_{n}^{p} \cdot x_{p+1}^{k} \\ = & n d \sum_{p=1}^{n}(-1)^{p} C_{n-1}^{p-1} x_{p+1}^{k} \\ = & -n d \sum_{q=0}^{n-1}(-1)^{q} C_{n-1}^{p} y_{q+1}^{k} . \end{aligned}
(let q=p1,yq+1=xp+1q=p-1, y_{q+1}=x_{p+1})
Since {xnnN}\left\{x_{n} \mid n \in N\right\} is an arithmetic sequence, {ynnN}\left\{y_{n} \mid n \in N\right\} is also an arithmetic sequence. Thus, by the induction hypothesis, we have
y=0n1(1)qCn1yyq+1k=0\sum_{y=0}^{n-1}(-1)^{q} C_{n-1}^{y} y_{q+1}^{k}=0

Therefore,
p=0n(1)pCnpxp+1k+1=0.\sum_{p=0}^{n}(-1)^{p} C_{n}^{p} x_{p+1}^{k+1}=0 .

By the principle of mathematical induction, the strengthened proposition is proved, and thus the original proposition is proved.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.