استقرا :‌

پایه :‌ $n=1$ ($1|2$)

فرض‌ : فرض می کنیم به ازای $n=k$ ء اگر $k+1$ عدد از مجموعه ی ${1, 2, 3, ... , 2k}$ داشته باشیم دو عدد وجود دارند به طوری که یکی دیگری را می شمارد.

اثبات $n=k+1$ :

$k+2$ عدد از مجموعه ی ${1, 2, 3, ... , 2k, 2k+1, 2k+2}$ در اختیار داریم.

حالت اول :‌ اگر حداقل یکی از اعداد$2k+1$ و $2k+2$ انتخاب نشده باشندء حداقل $k+1$ عدد از مجموعه ی ${1, 2, 3, ... , 2k}$ داریم که طبق فرض دو عدد وجود دارند یکی دیگری را می شمارد.

حالت دوم :‌هردو عدد $2k+1$ و $2k+2$ انتخاب شده باشند. در این صورت اگر $k+1$ را انتخاب کرده باشیم حکم ثابت می شودء در غیر اینصورت به جای عدد $2k+2$ء $k+1$ را انتخاب می کنیم. با این کار به حالت اول می رسیم ء پس دو عدد مانند $a$ و $b$ پیدا می شود که یکی دیگری را عاد کند. $(a|b)$

$a$ نمی تواند $k+1$ باشد چون $k+1$ هیچ عددی در بازه ی ۱ تا $2k$ را نمی شمارد. اگر ‌$b = k+1$ چون $k+1|2k+2$ نتیجه می دهد $a|2k+2$

اگر هیچکدام نیز $k+1$ نباشند در اعداد انتخاب شده هستند که حکم ثابت می شود.

پس در هر حالت دو عدد وجود دارند که یکی دیگری را می شمارد.

لانه کبوتری :

تعریف :‌ $odd(x)$ تابعی است که عامل های ۲ یک عدد را از تجزیه آن حذف می کند. متلا :‌

$odd(32) = 1 , odd(84) = 21$

اگر دنباله $n+1$ عددی اولیه به صورت زیر باشد :

$a_1, a_2 , ... , a_n , a_{n+1}$

دنباله $t$ به صورت زیر تعریف می شود :

$t_i = odd(a_i)$

تمامی اعداد دنباله $t$ عضوی از مجموعه ی $1 , 3 , 5 , ... , 2n-1$ هستند پس طبق اصل لانه کبوتری حداقل دو عضو از t هستند به طوری که $t_i = t_j = k$

می دانیم :

$a_i = k * 2 ^ x$

$a_j = k * 2 ^ y$

بدون کم شدن از کلیات مسأله فرض می کنیم $y>x$

در این صورت :

$a_j = a_i * 2 ^ {y-x}$

دو عدد پیدا شد که یکی دیگری را عاد می کند.