فوق العاده ساده هستش.

پایه استقرا: باید نشون بدیم که رابطه [tex]2^{n}[/tex] برای یک مجموعه صفر عنصری هم برقراره. یه مجموعه صفر عنصری همون مجموعه تهی هستش که فقط دارای یک زیر مجموعه هستش(تهی زیر مجموعه هر مجموعه ای است). از طرفی [tex]2^{0}=1[/tex]. پس پایه استقرا برقراره.

فرض استقرا: فرض می کنیم برای یک مجموعه n-1 عنصری تعداد زیر مجموعه های اون برابر با [tex]2^{n-1}[/tex] باشه.

گام استقرا: باید نشون بدیم که تعداد زیر مجموعه های یک مجموعه n عنصری برابر با [tex]2^{n}[/tex] هستش.
حالا چطور میشه این موضوع رو نشون داد.
اینطوری: طبق فرض استقرا یک مجموعه n-1 عنصری دارای [tex]2^{n-1}[/tex] عنصر هستش. حالا اگر به مجموعه اولیه یک عنصر جدید اضافه بشه طبیعتا تعداد زیر مجموعه ها افزایش پیدا خواهد کرد. تعداد زیر مجموعه های اضافه شده برابر با [tex]2^{n-1}[/tex] خواهد بود(کافیه به هر کدوم از زیرمجموعه های مجموعه n-1 عنصری عضو جدید رو اضافه کنیم.) یعنی حالا تعداد زیر مجموعه های یک مجموعه n عنصری برابر هست با [tex]2^{n-1} 2^{n-1}=2*2^{n-1}=2^{n}[/tex]

تمام

اگر n=1 میدونیم که یک مجموعه یک عضوی تعداد زیر مجموعه هاش دوتاس یکی خودش و یکی هم تهی.
فرض استقرا:حالا فرض میکنیم برا خود n حکممون درست باشه.یعنی داشته باشیم یه مجموعه مثل [tex]A=\left \{ a_{1},a_{2},...,a_{n} \right \}[/tex] که تعداد زیر مجموعه هاش [tex]2^{n}[/tex] تاست.

حکم استقرا: حالا ثابت میکنیم که برا یه مجموعه n+1 عضوی تعداد زیر مجموعه هاس [tex]2^{n 1}[/tex] تاست.

ما اگه یه عضو به مجموعه A اضافه کنیم میشه n+1 عضو.فرض کنیم اون مجموعه اینطوری باشه: [tex]B=\left \{ a_{1},a_{2},...,a_{n},b \right \}[/tex]
حالا زیر مجموعه های B میشه: خود زیرمجموعه های A + زیرمجموعه های A که عضو b رو بهشون اضافه کردیم.

فرض کنیم زیر مجموعه های A یعنی (P(A باشه : [tex]P(A)=\left \{ A_{1},A_{2},...,A_{n} \right \}[/tex]
حالا زیر مجموعه هایی که عضو b رو بهشون اضافه کردیم اسمشو بذاریم (P(D میشه :
[tex]P(D)=\left \{\left \{ b \right \}, \left \{ b,A_{2} \right \}\left \{ b,A_{3} \right \},...,\left \{b,A_{n} \right \} \right \}[/tex]


تعداد (P(A میشه [tex]2^{n}[/tex] و تعداد (P(D هم میشه[tex]2^{n}[/tex] . چون زیر مجموعه تهی A رو اسمشو گذاشتم [tex]A_{1}[/tex] و جاش {b} رو نوشتم و باز تعدادش میشه ۲ به توان n .

حالا [tex]P(B)=P(A) P(D)=2^{n} 2^{n}=2^{n 1}[/tex]

پس ما ثابت کردیم تعداد زیر مجموعه های n+1 عضوی هم میشه [tex]2^{n 1}[/tex].