Maths Olympiad Prep

Library / /486 of 520

Algebra Difficulty 6.3 National olympiad Prove it

18. (18 points) Given the sequence {xn}\left\{x_{n}\right\}. Prove: There exists a unique decomposition xn=ynznx_{n}=y_{n}-z_{n}, where the sequence {yn}\left\{y_{n}\right\} is non-negative, {zn}\left\{z_{n}\right\} is non-decreasing, and yn(znzn1)=0,z0=0y_{n}\left(z_{n}-z_{n-1}\right)=0, z_{0}=0.

Solution

18. Prove by mathematical induction.

When n=1n=1,
y1(z1z0)=y1z1=0{y1=0,z1=x1 or {y1=x1,z1=0. \begin{array}{l} y_{1}\left(z_{1}-z_{0}\right)=y_{1} z_{1}=0 \\ \Rightarrow\left\{\begin{array} { l } { y _ { 1 } = 0 , } \\ { z _ { 1 } = - x _ { 1 } } \end{array} \text { or } \left\{\begin{array}{l} y_{1}=x_{1}, \\ z_{1}=0 . \end{array}\right.\right. \end{array}

If x10x_{1} \geqslant 0, then {y1=x1z1=0;\left\{\begin{array}{l}y_{1}=x_{1} \\ z_{1}=0 ;\end{array}\right.
If x1<0x_{1}<0, then {y1=0,z1=x1.\left\{\begin{array}{l}y_{1}=0, \\ z_{1}=-x_{1} .\end{array}\right.
Therefore, when n=1n=1, the proposition holds.
Assume that when n=k(k1)n=k(k \geqslant 1), the proposition holds.
Then when n=k+1n=k+1, the problem is equivalent to
{yk+1(zk+1zk)=xk+1+zk,yk+1(zk+1zk)=0,yk+10,zk+1zk0,z0=0 \left\{\begin{array}{l} y_{k+1}-\left(z_{k+1}-z_{k}\right)=x_{k+1}+z_{k}, \\ y_{k+1}\left(z_{k+1}-z_{k}\right)=0, \\ y_{k+1} \geqslant 0, \\ z_{k+1}-z_{k} \geqslant 0, z_{0}=0 \end{array}\right.
{yk+1=0,zk+1zk=(xk+1+zk) or {yk+1=xk+1+zk,zk+1zk=0. \begin{array}{l} \Rightarrow\left\{\begin{array}{l} y_{k+1}=0, \\ z_{k+1}-z_{k}=-\left(x_{k+1}+z_{k}\right) \end{array}\right. \text { or } \\ \left\{\begin{array}{l} y_{k+1}=x_{k+1}+z_{k}, \\ z_{k+1}-z_{k}=0 . \end{array}\right. \end{array}

If xk+1+zk0x_{k+1}+z_{k} \geqslant 0, then {yk+1=xk+1+zk,zk+1=zk;\left\{\begin{array}{l}y_{k+1}=x_{k+1}+z_{k}, \\ z_{k+1}=z_{k} ;\end{array}\right.

Hence, when n=k+1n=k+1, the proposition holds.
By mathematical induction, the proposition holds for any natural number nn.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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