תורת הקבוצות/קבוצת החזקה: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
MeRabbit (שיחה | תרומות)
הרחבה - קבוצת החזקה
שורה 41:
מכאן, מנכונות בסיס וצעד האינדוקציה ועיקרון האינדוקציה, הטענה נכונה לכל n. כנדרש.
 
===הוכח
===הוכחה קומבינטורית===
ההוכחה הזו מניחה ידע קומבינטורי שהקורא יכול לוודא בספר מתאים בנושא, או בקורס במתמטיקה דיסקרטית.
 
טענה 1: מספר האפשרויות לבחור k עצמים שונים בלי חשיבות לסדר, מתוך n עצמים, נתון על ידי
<center>
<math>\binom{n}{k} = \frac{n!}{k!\left( n-k\right) ! }</math>
</center>
 
טענה 2: נוסחאת הבינום של ניוטון לכל <math>x\in\mathbb{R}</math> מתקיים ש:
<center>
<math>\ \left( 1+x\right)^n=\sum_{k=0}^{n}\binom{n}{k}x^k</math>
</center>
 
כעת, נשים לב שבהינתן קבוצה סופית A בעלת n איברים, כמות התת-קבוצות של A שיש בהן בדיוק k איברים הוא <math>\binom{n}{k}</math>, לכן,
<center>
<math>\ \vert 2^A\vert = \sum_{k=0}^{n}\binom{n}{k}</math>
</center>
 
לכן, על ידי הצבה של x=1 בנוסחת הבינום של ניוטון, נקבל:
<center>
<math>2^n =\left( 1+ 1\right)^n=\sum_{k=0}^{n}\binom{n}{k}=\vert 2^A\vert </math>
</center>
כנדרש.
 
===הוכחה באמצעות עוצמות===