k≥2k \ge 2k≥2 を任意に固定し、ステップ2より aik−aq=k′apa_{i_k} - a_q = k'a_paik−aq=k′ap となる整数 k′k'k′ を書く。部分列は狭義単調増加なので k≥2k \ge 2k≥2 で aik>aqa_{i_k} > a_qaik>aq であり、したがって k′ap>0k'a_p > 0k′ap>0、さらに ap>0a_p > 0ap>0 より k′>0k' > 0k′>0、すなわち k′k'k′ は正の整数である。整理すると aik=k′⋅ap+1⋅aqa_{i_k} = k' \cdot a_p + 1 \cdot a_qaik=k′⋅ap+1⋅aq となり、これはまさに目標の形 xap+yaqxa_p + ya_qxap+yaq（x=k′x = k'x=k′、y=1y = 1y=1、ともに正の整数）であり、q>pq > pq>p も満たされている。