در ابتدای اثبات به تعریف چند عمل میپردازیم:

عمل جابه جایی دو به دو: این عمل را برای رشته هایی به فرم $XXYY$ انجام میدهیم. ($X \ne Y$ و همچنین {$A,B,C$}$X,Y \in $) فرض کنید حرف سوم (یعنی حرف دیگری از مجموعه ی {$A,B,C$} که برابر با هیچکدام از $X$ و $Y$ نباشد) برابر $Z$ باشد. حال با این عمل $XXYY$ را به $YYXX$ تبدیل میکنیم:

$XXYY \to XZZY \to YYZY \to YYXX$

عمل یک به سه: این عمل را برای رشته هایی به فرم $XYYY$ انجام میدهیم. ($X \ne Y$ و همچنین {$A,B,C$}$X,Y \in $) فرض کنید حرف سوم (یعنی حرف دیگری از مجموعه ی {$A,B,C$} که برابر با هیچکدام از $X$ و $Y$ نباشد) برابر $Z$ باشد. با این عمل $XYYY$ را به $XXXX$ تبدیل میکنیم. اینکار را به این صورت انجام میدهیم:

$XYYY \to ZZYY \to ZXXY \to YYXY \to YZZY \to XXZY \to XXXX$

عمل تکمیل 1: این عمل برای رشته هایی به فرم $XXYYZ$ انجام میدهیم. ($Y \ne Z $، $X \ne Y$ ، $X \ne Y$و همچنین {$A,B,C$}$X,Z,Y \in $) و طی آن رشته ی $XXYYZ$ را به رشته ی $ZZZZZ$ تبدیل میکنیم. این عمل را به صورت زیر انجام میدهیم:

$XXYYZ \to XZZYZ \to YYZYZ \to YXXYZ \to ZZXYZ \to ZZZZZ$

عمل تکمیل 2: این عمل را برای رشته ی به فرم $XXYYZZ$ انجام میدهیم و طی آن $XXYYZZ$ را به $ZZZZZZ$ تبدیل میکنیم. برای این عمل کافیست که 5 حرف اول رشته را با توجه به عمل تکمیل یک به $Z$ تبدیل کنیم.

حال با استفاده از چهار عمل گفته شده به اثبات حکم میپردازیم.

لم1: اگر $D$ یک رشته باشد که در آن دستکم دوتا از $r_a$، $r_b$ و $r_c$ برابر باشند، آنگاه اگر محسن دو حرف متوالی و متفاوت از رشته را درنظر بگیرد و آنها را با حرف سوم جایگزین کند، باز هم ، دستکم 2 تا از $r_a$ ، $r_b$ و $r_c$ با هم برابرند.

اثبات: دو حالت زیر را بررسی میکنیم:

حالت1: $r_a=r_b=r_c$: در این صورت وقتی دو حرف متوالی از رشته را تغییر میدهیم از تعداد هر دوی این دو حرف، در رشته دقیقا یک واحد کم میشود. در نتیجه از آنجا که قبل از این عمل باقیمانده ی آنها بر 3 یکسان بوده است، باقیمانده ی آنها، همچنان یکسان باقی میماند. پس باز هم دستکم دو تا از $r_a$، $r_b$ و $r_c$ با هم برابر هستند.

حالت2: دو تا از $r_a$، $r_b$ و $r_c$ با هم برابر و نابرابر با دیگری باشند: بدون از دست رفتن کلیت مسئله فرض کنید $r_a=r_b \ne r_c$. اگر تعداد دو حرف متوالی که انتخاب کردیم باقیمانده ی یکسانی بر 3 داشته باشند، با استدلالی مشابه حالت1 ، بعد از انجام تغییر باز هم تعداد آنها باقیمانده ی یکسانی بر عدد 3 دارند. حال فرض کنید تعداد دو حرف متوالی باقیمانده ی یکسانی بر 3 نداشته باشند. یعنی ما یا $AC$ و یا $BC$ را برای تغییر انتخاب کرده باشیم. طی تغییرمان از تعداد $A$ یک واحد کم به تعداد $B$ دو واحد اضافه میشود. در نتیجه اختلاف تعداد $A$ و $B$ ، 3 تا تغییر میکند. از آنجا که $r_a=r_b$ بوده است، پس اختلاف تعداد $B$ و $A$ در رشته ی $D$ بر 3 بخش پذیر بوده و طی عمل انجام شده این اختلاف همچنان بخش پذیر بر 3 باقی میماند. در نتیجه باز هم $r_a=r_b$ است.

پس با توجه به حالت1 و حالت2 حکم ثابت میشود.

حال حکم مسئله را با استقرا اثبات میکنیم. حکم به ازای $n=1$، $n=2$ و $n=3$ صحیح است. درستی هر کدام را در زیر بررسی کرده ایم:

$n=1$ : در این حالت رشته به فرم $X$ است. پس تمام حروف رشته با هم برابرند.

$n=2$: در این حالت اگر هر دو حرف رشته با هم برابر باشند که مشکلی نیست. در غیر این صورت رشته به فرم $XY$ ($X \ne Y$ و همچنین {$A,B,C$}$X,Y \in $) است. پس تنها با یک عمل میتوان آن را به رشته ی$ZZ$ تبدیل کرد. (منظور از $Z$ حرف سوم مجموعه ی {$A,B,C$} به غیر از $X$ و $Y$ است)

$n=3$: در این حالت یا تمام حروف رشته با هم برابرند که مشکلی نیست و یا رشته به فرم $XYZ$ ($Y \ne Z $، $X \ne Y$ ، $X \ne Y$و همچنین {$A,B,C$}$X,Z,Y \in $) است. زیرا اگر رشته 2 حرف $X$ و یک حرف $Y$ داشته باشد ($X \ne Y$) آنگاه $r_X=2$ و $r_Y=1$ و $r_Z=0$ است (منظور از $Z$ حرف سوم مجموعه ی {$A,B,C$} به غیر از $X$ و $Y$ است). پس رشته باید به فرم $XYZ$ باشد که در این صورت نیز با یک عمل به روی $XY$ میتوان رشته را به $ZZZ$ تبدیل کرد.

حال فرض کنید حکم به ازای تمامی $k$ ها به طوری که $k \lt n$ صحیح باشد. ثابت میکنیم حکم به ازای $n=k$ نیز صحیح است. همچنین میدانیم $n \ge 4$. در ابتدا از اول رشته شروع میکنیم و حروف را 2 تا 2 تا جدا میکنیم. در نتیجه اگر $n$ زوج باشد حروف به $\frac {n} {2}$ دسته ی 2 تایی و اگر $n$ فرد باشد به $\frac {n-1} {2}$ تا دسته ی 2 تایی و یک دسته ی یکتایی تقسیم میشوند. حال در هر دسته حروف را با هم برابر میکنیم. بدین صورت که اگر حروف یک دسته با هم برابر نبودند، با یک عمل حروف آن را به حرف سوم تبدیل میکنیم. حالات زیر را بررسی میکنیم:

حالت1: $n$ زوج باشد: در این صورت حروف به $\frac {n} {2}$ دسته ی 2 تایی تقسیم شده اند. حروف را به وسیله ی عمل جابه جایی دو به دو طوری میچینیم که هرکدام از حروف $A$ ، $B$ و $C$ به صورت متوالی قرار گیرند. مثلا اگر رشته ما بصورت $AABBCCAA$ بود رشته را به صورت $AAAABBCC$ در می آوریم. واضح است که اینکار با عمل جابه جایی دو به دو به راحتی قابل انجام است. زیرا میتوانیم هر دو جفت متوالی را با هم جابه جا کنیم. از طرفی این کار را میتوانیم به گونه ای انجام دهیم. که حرفی که بیشترین تعداد ممکن را داشته باشد در ابتدای رشته باشد. مثلا در رشته ی $AABBCCAA$ ، $َA$ بیشترین تعداد را دارد. پس رشته را به $AAAABBCC$ تبدیل میکنیم. حال اگر تعداد بیشترین حرف حداقل 4 بباشد، سه حرف اول رشته را برمیداریم. فرض کنید این سه حرف $X$ بوده اند. از آنجا که این سه حرف یکسانند، پس هیچکدام از $r_a$، $r_b$ و $r_c$ تغییر نمیکنند. همچنین با توجه به لم1 ، چون در ابتدا دو تا از $r_a$، $r_b$ و $r_c$ یکسان بوده اند، همچنان 2تا از $r_a$، $r_b$ و $r_c$ با هم برابرند. پس یک رشته به طول $n-3 \ge 1$ باقی میماند که با توجه به استقرا میتوانیم آن را به رشته ای تبدیل کنیم که تمام حرفش برابرند. فرض کنید تمام $n-3$ حرف آخر را به $Y$ تبدیل کنیم. پس رشته ای به فرم زیر داریم:

$XXXYY...Y$

اگر $X=Y$ باشدکه تمام حروف رشته با هم برابرند. در غیر اینصورت 4 حرف اول رشته را در نظر بگیرید. این چهار حرف به فرم $XXXY$ هستند. ($X \ne Y$) پس میتوانیم با استفاده از عمل یک به سه آن را به فرم $YYYY$ تبدیل کنیم. در نتیجه تمام حروف رشته برابر $Y$ میشوند.

حال فرض کنید تعداد بیشترین حرف ، حداکثر 2 است. در اینصورت رشته ی ما یا به فرم $XXYYZZ$ است ($X \ne Y , X \ne Z , Y \ne Z$) که میتوانیم با استفاده از عمل تکمیل 2 ، همه ی آنها را به $Z$ تبدیل کنیم و یا به فرم $XXYY$ است ($X \ne Y$) که برای آن میتوانیم کار های زیر را انجام دهیم. (منظور از $Z$ حرف سوم مجموعه ی {$A,B,C$} به غیر از $X$ و $Y$ است):

$XXYY \to XZZY \to YYZY \to YXXY \to ZZXY \to ZZZZ$

اگر هم تمام حروف با هم برابر بودند که مشکلی نیست.

پس با توجه به استدلال گفته شده، حکم استقرا برای $n$ های زوج ثابت میشود.

حالت2: $n$ فرد باشد: در این صورت رشته به $\frac {n-1}{2}$ دسته ی 2 تایی و یک دسته ی یکتایی تقسیم شده است. مانند حالت1 با استفاده از عمل جابه جایی دوبه دو میتوانیم حروف یکسان در بین $n-1$ حرف اول را در کنار هم قرار دهیم. اما این عمل را ایندفعه بگونه ای انجام میدهیم که اگر حرف آخر رشته ی $X$ باشد، حروف $X$ در آخر $n-1$ حرف قرار گیرند. به عبارتی تمام حروف $X$ کنار هم قرار گیرند. علاوه براین بین دو حرف دیگر، آن حرفی که تعداد بیشتری دارد در ابتدای رشته قرار گیرد. برای مثال فرض کنید رشته ی ما به صورت $AABBAACCBBAAC$ باشد. پس ما آن را با استفاده از جابه جایی دو به دو به رشته ی $AAAAAABBBBCCC$ تبدیل میکنیم.پس فرض کنید رشته به فرم زیر درآید:

$ZZ...ZYY..YXX..X$

همچنین فرض کنید از حرف $Z$ ، $z$ تا ، از حرف $Y$ ، $y$ تا و از حرف $X$ ، $x$ تا داریم. میدانیم $z \ge y$

سه حالت به وجود می آید:

حالت1: $x \ge 3$ : در اینصورت 3 حرف آخر رشته را برمیداریم و با توجه به فرض استقرا و لم1 و اینکه باضیمانده ی $r_a$، $r_b$ و $r_c$ ثابت می ماند می توانیم $n-3$ حرف اول رشته را با هم برابر کنیم. در اینصورت رشته ی ما به فرم زیر در می آید:

$YY...YXXX$

حال اگر $X=Y$ بود ، تمام حروف رشته با هم برابرند. در غیر اینصورت چهار حرف آخر رشته را در نظر بگیرید که به فرم $YXXX $هستند ($X \ne Y$). پس به وسیله ی عمل یک به سه میتوانیم آن را به $YYYY$ تبدیل کنیم. پس تمام حروف رشته با هم برابر میشوند.

حالت2: $x<3$ و $z \ge 4$: در اینصورت، 3 حرف اول رشته را برمیداریم و با توجه به استقرا و لم1 و اینکه باقیمانده ی $r_a$ ، $r_b$ و $r_c$ بر 3 ثابت میماند میتوانیم $n-3$ حرف آخر رشته را با هم برابر کنیم. در اینصورت رشته ی ما به فرم زیر در می آید:

$ZZZYY...Y$

حال اگر $Z=Y$ باشد، تمام حروف با هم برابرند، در غیر اینصورت چهار حرف اول رشته را در نظر بگیرید که به فرم $ZZZY$ هستند ($Z \ne Y$) . پس به وسیله ی حرکت یک به سه میتوانیم آنها را به $YYYY$ تبدیل کنیم. پس تمام حروف رشته برابر میشوند.

حالت3:$x < 3 , z < 4$ : در اینصورت از آنجا که $n \ge 4$ است، پس رشته ی ما به فرم $ZZYYX$ است. ($X \ne Y , X \ne Z , Z \ne Y$) پس میتوانیم با استفاده از عمل تکمیل 1 رشته را به رشته ی $XXXXX$ تبدیل کنیم.

در نتیجه ی حالات1 و 2 و 3 حکم استقرا برای $n$ های فرد نیز ثابت میشود.

در نتیجه حکم به ازای تمامی $n$ های زوج و فرد ثابت میشود.