استقرای ضعیف میزنیم روی n یعنی برای مجموعه ای با $2^n$ درسته برای$n+1$ میخوایم ثابت کنیم :

پایه :ابن را میدانیم برای مجموعه با 1 عضو درست است .

گام:

لم: میدانیم تعداد زیرمجموعه های با فرد تا عضو عددی زوج است .

اثبات : برهان خلف : فرض میکنیم تعداد فردی زیر مجموعه با فرد تا عضو داریم پس فرد تا عدد در این زیر مجموعه ها یعنی اشتراک انها داریم واشتراک زیر مجموعه های دیگر که زوج تا عضو دارند عددی زوج است پس با توجه به این دو بخش اشتراک کل آنها باید مجموعه کل شود پس یعنی: زوج + فرد = زوج که تناقض است پس فرض خلف باطل و حکم بر قرار است.

حال زیر مجموعه های با فرد تا عضوی دو تا دوتا با هم میگیریم و به اندازه تعداد اعضای زیر مجموعه کوچک تره از زیر مجموعه بزرگ تر بر میداریم .

الان ثابت میشود همه زیر مجموعه ها تعداد زوجی عضو دارند (اثباتش بدیهی است )

حال در هر زیر مجموعه اعضای آن را به مجموعه های دوتایی افراز می کنیم و آن را مانند یک زوج مرتب مینویسیم

برای فهم این موضوع مثال زیر دقت کنید :

مثال برای یک مجموعه $6$ عضوی مانند {$ a,b,c,d,e,f $} آن را به {$(a,b)$,$(c,d)$,$(e,f)$}تبدیل میکنیم .

حال تعداد اعضای هر زیر مجموعه ها نصف میشود پس تعداد اعضای کل مجموعه نصف می شود و برابر $2^n$ می شود با توجه به فرض استقرا برای $n$درست است پس برای $n+1$ نیز طبق گام مسئله درست است $((:$

ممنون از خوندنتون سوال جالبی بود $^_^$

پ.ن:جواب درست است .