מתוך ויקיפדיה, האנציקלופדיה החופשית
זהות מקל ההוקי עבור n = 7,k = 3: סכום המספרים הירוקים שווה למספר האדום
בקומבינטוריקה , זהות פרמה (על שם המתמטיקאי הצרפתי פייר דה פרמה ) היא נוסחת הסיכום הבאה עבור מקדמים בינומיים באלכסון של משולש פסקל:
∑
i
=
k
n
(
i
−
1
k
−
1
)
=
(
n
k
)
{\displaystyle \sum _{i\,=\,k}^{n}{\binom {i-1}{k-1}}={\binom {n}{k}}}
. הזהות ידועה גם בתור זהות מקל ההוקי על שם צורתה הגאומטרית במשולש פסקל , המזכירה מקל הוקי .
תהי סדרה מונוטונית עולה בת
n
{\displaystyle n}
מספרים.
אגף ימין של הזהות מונה כמה דרכים ניתן לבחור
k
{\displaystyle k}
איברים מתוך
n
{\displaystyle n}
איברי הסדרה.
באגף שמאל, נבחר איבר
1
≤
i
≤
n
{\displaystyle 1\leq i\leq n}
כלשהו ולאחר מכן נבחר
k
−
1
{\displaystyle k-1}
מתוך
i
−
1
{\displaystyle i-1}
האיברים הקטנים ממנו. עבור
i
<
k
{\displaystyle i<k}
מתקיים
(
i
−
1
k
−
1
)
=
0
{\displaystyle {\binom {i-1}{k-1}}=0}
ולכן
∑
i
=
1
n
(
i
−
1
k
−
1
)
=
∑
i
=
k
n
(
i
−
1
k
−
1
)
=
(
n
k
)
{\displaystyle \sum _{i\,=\,1}^{n}{\binom {i-1}{k-1}}=\sum _{i\,=\,k}^{n}{\binom {i-1}{k-1}}={\binom {n}{k}}}
.
∑
i
=
0
n
−
1
(
1
+
x
)
i
=
(
1
+
x
)
n
−
1
x
∑
i
=
0
0
(
0
i
)
x
i
+
∑
i
=
0
1
(
1
i
)
x
i
+
⋯
+
∑
i
=
0
n
−
2
(
n
−
2
i
)
x
i
+
∑
i
=
0
n
−
1
(
n
−
1
i
)
x
i
=
∑
j
=
1
n
(
n
j
)
x
j
−
1
(
0
k
−
1
)
x
k
−
1
+
(
1
k
−
1
)
x
k
−
1
+
⋯
+
(
k
−
1
k
−
1
)
x
k
−
1
+
⋯
+
(
n
−
2
k
−
1
)
x
k
−
1
+
(
n
−
1
k
−
1
)
x
k
−
1
=
(
n
k
)
x
k
−
1
(
k
−
1
k
−
1
)
+
(
k
k
−
1
)
+
⋯
+
(
n
−
2
k
−
1
)
+
(
n
−
1
k
−
1
)
=
(
n
k
)
{\displaystyle {\begin{aligned}&\sum _{i\,=\,0}^{n\,-\,1}(1+x)^{i}={\frac {(1+x)^{n}-1}{x}}\\&\sum _{i\,=\,0}^{0}{\binom {0}{i}}x^{i}+\sum _{i\,=\,0}^{1}{\binom {1}{i}}x^{i}+\cdots +\sum _{i\,=\,0}^{n\,-\,2}{\binom {n-2}{i}}x^{i}+\sum _{i\,=\,0}^{n\,-\,1}{\binom {n-1}{i}}x^{i}=\sum _{j\,=\,1}^{n}{\binom {n}{j}}x^{j-1}\\&{\binom {0}{k-1}}x^{k-1}+{\binom {1}{k-1}}x^{k-1}+\cdots +{\binom {k-1}{k-1}}x^{k-1}+\cdots +{\binom {n-2}{k-1}}x^{k-1}+{\binom {n-1}{k-1}}x^{k-1}={\binom {n}{k}}x^{k-1}\\&{\binom {k-1}{k-1}}+{\binom {k}{k-1}}+\cdots +{\binom {n-2}{k-1}}+{\binom {n-1}{k-1}}={\binom {n}{k}}\end{aligned}}}
∑
i
=
k
n
(
i
−
1
k
−
1
)
=
∑
i
=
k
n
[
(
i
k
)
−
(
i
−
1
k
)
]
=
∑
i
=
k
n
(
i
k
)
−
∑
i
=
k
n
(
i
−
1
k
)
=
∑
i
=
k
n
(
i
k
)
−
∑
i
=
k
n
−
1
(
i
k
)
=
(
n
k
)
{\displaystyle {\begin{aligned}\sum _{i\,=\,k}^{n}{\binom {i-1}{k-1}}&=\sum _{i\,=\,k}^{n}\left[{\binom {i}{k}}-{\binom {i-1}{k}}\right]\\&=\sum _{i\,=\,k}^{n}{\binom {i}{k}}-\sum _{i\,=\,k}^{n}{\binom {i-1}{k}}\\&=\sum _{i\,=\,k}^{n}{\binom {i}{k}}-\sum _{i\,=\,k}^{n\,-\,1}{\binom {i}{k}}\\&={\binom {n}{k}}\end{aligned}}}
הוכחה באינדוקציה מתמטית אפשר להיווכח גם בצורה חזותית, המספר הקיצוני ב"מקל" הוא תמיד סכום שני המספרים שמעליו, אחד מהם הוא הקיצוני במקל הקצר ממנו בשורה אחת. כמובן שבמקל על שתי שורות המספר התחתון הוא העוקב של המספר שאינו 1.
עבור
n
=
k
{\displaystyle n=k}
נקבל
∑
i
=
k
n
(
i
−
1
k
−
1
)
=
∑
i
=
k
k
(
i
−
1
k
−
1
)
=
1
=
(
k
k
)
=
(
n
k
)
{\displaystyle \sum _{i\,=\,k}^{n}{\binom {i-1}{k-1}}=\sum _{i\,=\,k}^{k}{\binom {i-1}{k-1}}=1={\binom {k}{k}}={\binom {n}{k}}}
.
נניח כי הזהות מתקיימת עבור
n
{\displaystyle n}
, ונוכיח כי היא מתקיימת עבור
n
+
1
{\displaystyle n+1}
(באמצעות זהות פסקל):
∑
i
=
k
n
+
1
(
i
−
1
k
−
1
)
=
∑
i
=
k
n
(
i
−
1
k
−
1
)
+
(
n
k
−
1
)
=
(
n
k
)
+
(
n
k
−
1
)
=
(
n
+
1
k
+
1
)
{\displaystyle \sum _{i\,=\,k}^{n\,+\,1}{\binom {i-1}{k-1}}=\sum _{i\,=\,k}^{n}{\binom {i-1}{k-1}}+{\binom {n}{k-1}}={\binom {n}{k}}+{\binom {n}{k-1}}={\binom {n+1}{k+1}}}
ערך זה הוא
יתום , כלומר אין ערכים בוויקיפדיה ש
מקשרים אליו . אתם מוזמנים
לתרום לוויקיפדיה ו
לקשר אליו מ
כמה מהערכים שמכילים את המונח "זהות פרמה" .