A színek számára vonatkozó teljes indukcióval bizonyítunk. 1 színre nyilvánvaló az állítás. Tegyük fel ezért, hogy $n-1$ szín esetére már igazoltuk az állítást, és nézzük meg, mit tudunk mondani $n$ szín mellett. A természetes számokat színezzük ki az $s_1$, $s_2$, $\text{...}$, $s_n$ színekkel. Feltehetjük, hogy az $s_1$, $s_2$, $\text{...}$, $s_{n-1}$ színek egyike sem teljesíti a feladatban kirótt feltételt, hiszen különben készen vagyunk. Tekintsük az $s_{n-1}$ és az $s_n$ színű számokat együttesen $s\text{'}$ színűeknek. Ekkor az indukciós feltevés miatt az $s_1$, $s_2$, $\text{...}$, $s_{n-2}$, $s\text{'}$ színek valamelyike teljesíti a feladatban kirótt feltételt, ez a szín pedig az előbbi megjegyzésünk folytán csakis az $s\text{'}$ lehet. Így alkalmas $m$-mel minden $k$-hoz található $s\text{'}$ színű $a_1$, $a_2$, $\text{...}$, $a_k$ úgy, hogy $0<a_{j+1}-a_j\le m(1\le j\le k-1$) teljesüljön. Rögzítsük le az $m$-et. Mivel az $s_{n-1}$ nem teljesíti a feladatbeli feltételt, azért van olyan pozitív egész $l$, amelyhez nem található $s_{n-1}$ színű $a_1$, $a_2$, $\text{...}$, $a_l$ úgy, hogy $0<a_{j+1}-a_j\le m$ ($1\le j\le l-1$) fennálljon. Rögzítsük le ezt az $l$-et is. Be fogjuk látni, hogy $2lm$-mel az $s_n$ szín kielégíti a feladatbeli feltételt. Legyen ehhez $k$ tetszőleges pozitív egész, és válasszuk meg az $s\text{'}$ színű $a_1$, $a_2$, $\text{...}$, $a_{kl}$ számokat úgy, hogy $0<a_{j+1}-a_j\le m$  ($1\le j\le kl-1$) teljesüljön. Ekkor az $l$ választása folytán tetszőleges $1\le p\le k$ mellett kell lennie egy $s_n$ színű $A_p$ számnak az egymást követő $a_{\left(p-1\right)l+1}$, $a_{\left(p-1\right)l+2}$, $\text{...}$, $a_{pl}$ között. Az $A_1$, $A_2$, $\text{...}$, $A_k$ számokra teljesülnek a