به استقرا‌ی قوی روی $n$ حکم را ثابت می‌کنیم. برای پایه‌ی استقرا $n=3$ و $n= 4$ را در نظر می‌گیریم. تنها حالت ممکن برای $n=3$، شکل (۱) است که حسام می‌تواند کارش را مانند شکل (۲) انجام دهد:

تنها حالت ممکن نیز برای $n=4$ شکل (۳) است که حسام می‌تواند کارش را مانند شکل (۴) انجام دهد:

فرض کنید حکم به ازای $<n$ برقرار باشد. ثابت می‌کنیم حکم به ازای $n$ نیز برقرار است. یک درخت $n$ رأسی در نظر بگیرید و آن را ریشه‌دار کنید. چند حالت داریم:

• دو برگ سفید با پدر مشترک داشته باشیم؛ در این صورت روی یکی از آن دو برگ عدد ۱ و روی دیگری $-1$ می‌نویسیم و عدد بقیه‌ی رأس‌های سفید را $0$ می‌گذاریم. تمام شرایط برقرار و کار حسام انجام می‌شود.
• در صورتی که حالت بالا رخ ندهد، پایین‌ترین برگ را در نظر می‌گیریم و آن را $u$ می‌نامیم. دو حالت داریم:

1. این برگ سیاه باشد. فرض کنید $v$ پدر رأس $u$ باشد. $v$ را به همراه تمام فرزندان‌ش (از جمله $u$) از درخت حذف می‌کنیم. در درخت باقی‌مانده هم‌چنان تعداد رأس‌های سفید بیش‌تر است. هم‌چنین در درخت باقی‌مانده حداقل سه رأس وجود دارد؛ زیرا پدر $v$ رأسی سیاه است و بنابراین دست کم دو رأس سفید باید در درخت باقی‌مانده موجود باشند. پس درخت باقی‌مانده یک درخت معتبر است و می‌توانیم طبق فرض استقرا آن را به طور معتبر عددگذاری کنیم. حال عدد $v$ را صفر می‌گذاریم. تمام شرایط برقرار و کار حسام انجام می‌شود.
2. این برگ سفید باشد. در این صورت فرض کنید پدر $u$ یک رأس سیاه مانند $v$ باشد. $v$ فرزند دیگری ندارد. $u, v$ را از درخت حذف می‌کنیم. یک درخت $n-2$ رأسی معتبر به دست می‌آید و طبق فرض استقرا می‌توان آن را به صورت معتبر عددگذاری کرد. حال فرض کنید عدد پدر رأس $v$ (که رأسی سفید است)، برابر $x$ باشد. عدد رأس $u$ را برابر $-x$ می‌گذاریم. تمام شرایط برقرار و کار حسام انجام می‌شود.