מספר משולשי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מאין תקציר עריכה |
←הוכחה קומבינטורית: שכתוב |
||
שורה 16:
הטיעון של גאוס הוא למעשה הוכחה לתקפות הנוסחה לסכום של סדרה חשבונית.
===הוכחה
[[קובץ:Complete graph K7.svg|ממוזער|ב[[גרף שלם]] עם 7 צמתים יש <math>T_6</math> קשתות]]
n+1 מכרים נפגשים במסיבה. כל אחד לוחץ פעם אחת את היד לכל אחד אחר במסיבה. כמה לחיצות ידיים היו במסיבה? (בניסוח פורמלי יותר, כמה קשתות יש ב[[גרף שלם]] עם n+1 צמתים?) נספור אותם באופן הבא: נבחר איש ראשון. ישנם n אנשים אחרים במסיבה שלכל אחד מהם לחץ את היד. נספור n לחיצות ונוציא את האיש הראשון מהמסיבה. נבחר איש שני. נשארו n-1 אנשים במסיבה שלכל אחד מהם הוא לוחץ את היד. נספור עוד n-1 לחיצות ונוציא את האיש השני מהמסיבה. לאיש השלישי ישארו רק n-2 לחיצות. נספור אותן ונוציאו, וכן הלאה, עד שנגיע לאיש האחרון במסיבה שיוותרו לו 0 לחיצות לבצע. בסך הכל קיבלנו שמספר לחיצות הידיים הוא:
:<math>\ n+(n-1)+\ldots+2+1+0 = T_n</math>
מצד שני ישנה דרך חכמה יותר לספור לחיצות ידיים. מ[[עקרון הכפל]] יש <math>(n+1)^2</math> זוגות אפשריים של אנשים במסיבה. אולם בדרך זו גם ספרנו אנשים שהם זוג של עצמם. יש n+1 זוגות כאלו (אחד לכל איש) ולכן יש <math>n^2-(n+1)</math> זוגות אפשריים שכוללים שני אנשים שונים. נשים לב כי ספרנו פעמיים כל זוג. פעם אחת את הזוג פלוני-אלמוני ופעם נוספת את הזוג אלמוני-פלוני. מכאן שכדי לקבל את מספר הזוגות האמיתי יש לחלק ב-2. כעת קיבלנו את מספר הזוגות האמיתי שהוא:
<math>\frac{(n+1)^2-(n+1)}{2}=\frac{n(n+1)}{2}</math>
זהו גם מספר לחיצות הידיים, שכן כל זוג לוחץ ידיים פעם אחת בדיוק.
מכיוון ששתי הדרכים לספור את הזוגות צריכות לתת תוצאה זהה, קיבלנו שוויון בין התוצאה בשיטה הראשונה לתוצאה בשיטה השנייה. לכן:▼
▲מכיוון ששתי הדרכים לספור
:<math>\ T_n = \frac{n(n+1)}2</math>
| |||