Raisonnons par récurrence sur n ≥1 .
Pour n =1 : ok
Supposons la propriété établie au rang n .
Par l’absurde supposons que A soit une partie de n +2 entiers distincts tous inférieurs ou égaux à 2n +2 .
Indexons les éléments de A par ordre croissant :
{a_0 ,a_1 , ... , a_(n+1) } avec a_i <a_(i+1) .
Si a_n ≤2n alors l’ensemble {a_0 ,a_1 , ... , a_(2n) } est contraire à l’hypothèse de récurrence.
Sinon a_n =2n+1 et a_(n+1)=2n+2 . Puisque n+1| a_(n+1) , nécessairement n+1 ∉ {a_0 ,a_1 , ... , a_(n-1) }
Considérons alors {a_0 ,a_1 , ... , a_(n-1) }U {n+1 }
C’est une partie à n +1 éléments tous inférieur ou égaux à 2n .
Par hypothèse de récurrence, l’un d’eux divise l’autre et il en est donc de même dans {a_0 ,a_1 , ... , a_(n+1) }.
Ceci induit une contradiction avec l’hypothèse de départ.
Récurrence établie.
Accueil 
