До­ка­жем это утвер­жде­ние ин­дук­ци­ей по n.

База при

При разобьём на мно­жеств а {1, 2} и {3}, от­но­ше­ние равно что мень­ше При разобьём на мно­же­ства {1, 2, 3} и {4}, От­но­ше­ние будет что как раз равно

При разобьём на мно­же­ства {1, 2, 5} и {3, 4}. От­но­ше­ние равно что мень­ше

Пе­ре­ход ин­дук­ции от n к при Пусть у нас есть раз­би­е­ние чисел от 1 до n, удо­вле­тво­ря­ю­щее усло­вию. До­ба­вим в мно­же­ство с мень­шим про­из­ве­де­ни­ем число а в мно­же­ство с боль­шим про­из­ве­де­ни­ем P₂ число

До­ка­жем, что про­из­ве­де­ния от­ли­ча­ют­ся не более чем в раз. Так как то

С дру­гой сто­ро­ны, так как то

До­ка­жем, что это не боль­ше Это рав­но­силь­но

что верно при Таким об­ра­зом, пе­ре­ход, до­ка­зан.