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

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

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

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

تمام

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

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

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

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


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

حالا $P(B)=P(A) P(D)=2^{n} 2^{n}=2^{n 1}$

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