Maths Olympiad Prep

Track / Stage 8 / 64 of 180 #1764 of 1964

Problem 1764

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

3.92 {xn∣n∈N}\left\{x_{n} \mid n \in N\right\} is a sequence of real numbers, and for each positive integer n⩾2n \geqslant 2, we have
x1−Cn1x2+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,1⩽k⩽n−1k, n, 1 \leqslant k \leqslant n-1, we have
∑p=0n(−1)pCnp⋅xp+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.

Next problem →

Official solution

[Proof] Take the arithmetic sequence {an∣n∈N}\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=x2−x1d=x_{2}-x_{1}.

Notice that
∑p=0n(−1)pCnpap+1=∑p=0n(−1)pCnp(a1+pd)=a1∑p=0n(−1)pCnp+d∑p=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=p⋅n!p!(n−p)!=n⋅(n−1)!(p−1)!(n−p)!=nCn−1p−1,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=(1−1)n=∑p=0n(−1)pCnp,0=(1−1)n−1=∑q=0n−1(−1)qCn−1q=∑p=0n(−1)p−1Cn−1p−1, (let q=p−1 ) \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=d∑p=1n(−1)pnCn−1p−1=−dn∑p=1n(−1)p−1Cn−1p−1=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
x1−Ck1x2+Ck2x3−⋯+(−1)k−1Ckk−1xk+(−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
a1−Ck1a2+Ck2a3−⋯+(−1)k−1Ckk−1ak+(−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+1−ak+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,n∈Nx_{n}=a_{n}, n \in N.
In other words, the sequence {xn∣n∈N}\left\{x_{n} \mid n \in N\right\} given in the problem is an arithmetic sequence.
Next, we prove a strengthened proposition: If {xn∣n∈N}\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 k∈N,n⩾k+1k \in N, n \geqslant k+1.
Clearly, from the above discussion, the strengthened proposition holds for k=1k=1 for all n⩾k+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 n⩾k+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)pCnp⋅xp+1k⋅xp+1=∑p=0n(−1)pCnpxp+1k⋅(x1+pd)=x1∑p=0n(−1)pCnpxp+1k+d∑p=0n(−1)p⋅p⋅Cnp⋅xp+1k=nd∑p=1n(−1)pCn−1p−1xp+1k=−nd∑q=0n−1(−1)qCn−1pyq+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=p−1,yq+1=xp+1q=p-1, y_{q+1}=x_{p+1})
Since {xn∣n∈N}\left\{x_{n} \mid n \in N\right\} is an arithmetic sequence, {yn∣n∈N}\left\{y_{n} \mid n \in N\right\} is also an arithmetic sequence. Thus, by the induction hypothesis, we have
∑y=0n−1(−1)qCn−1yyq+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 reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.