Ταυτότητα του Πασκάλ

Στα μαθηματικά, η ταυτότητα του Πασκάλ είναι η εξής ταυτότητα που ισχύει για κάθε φυσικούς αριθμούς $0\leq k\leq n$,

${\binom {n+1}{k+1}}={\binom {n}{k+1}}+{\binom {n}{k}},$

όπου ${\tbinom {x}{y}}$ είναι ο διωνυμικός συντελεστής.

Η ταυτότητα αυτή μπορεί να χρησιμοποιηθεί για τον υπολογισμό των διωνυμικών συντελεστών μέσω της κατασκευής του λεγόμενου τριγώνου του Πασκάλ. Ονομάζεται από τον μαθηματικό Μπλεζ Πασκάλ.

Αποδείξεις

Αλγεβρική απόδειξη

Υπενθυμίζουμε τον ορισμό του διωνυμικού συντελεστή,

${\binom {n}{k}}={\frac {n!}{(n-k)!k!}},$

όπου $n!=n\cdot (n-1)\cdot \ldots \cdot 1$ είναι το παραγοντικό του $n$.

Από τον ορισμό του διωνυμικού συντελεστή, έχουμε ότι

${\begin{aligned}{\binom {n}{k+1}}+{\binom {n}{k}}&={\frac {n!}{(n-k-1)!(k+1)!}}+{\frac {n!}{(n-k)!k!}}\\&={\frac {n!}{(n-k-1)!k!}}\cdot \left({\frac {1}{k+1}}+{\frac {1}{n-k}}\right)\\&={\frac {n!}{(n-k-1)!k!}}\cdot \left({\frac {n-k+k+1}{(k+1)\cdot (n-k)}}\right)\\&={\frac {(n+1)!}{(n-k)!(k+1)!}}\\&={\binom {n+1}{k+1}}.\end{aligned}}$

Συνδυαστική απόδειξη

Παράδειγμα για $n=5$ για τις δύο περιπτώσεις της συνδυαστικής απόδειξης.

Υπενθυμίζουμε ότι ο διωνυμικός συντελεστής ${\tbinom {n}{k}}$ μετράει το πλήθος των συνδυασμών $k$ στοιχείων που μπορούν να επιλεχθούν από συνολικά $n$ στοιχεία.

Επομένως, ο συντελεστής ${\tbinom {n+1}{k+!}}$ μετράει το πλήθος των συνδυασμών για να διαλέξουμε $k+1$ από $n+1$ στοιχεία. Έστω ότι τα στοιχεία είναι $\{1,2,\ldots ,n+1\}$, τότε διαχωρίζουμε τις εξής δύο περιπτώσεις σε αυτούς τους συνδυασμούς:

1. Διαλέγουμε το $n+1$ και $k$ στοιχεία από τα $\{1,\ldots ,n\}$.
2. Διαλέγουμε $k+1$ στοιχεία από τα $\{1,\ldots ,n\}$.

Για την πρώτη περίπτωση υπάρχουν ${\tbinom {n}{k}}$ τρόποι και για την δεύτερη ${\tbinom {n+1}{k+1}}$ τρόποι, άρα το άθροισμά τους μας δίνει το συνολικό πλήθος των συνδυασμών $k+1$ από $n+1$ στοιχεία, επομένως

${\binom {n}{k+1}}+{\binom {n}{k}}={\binom {n+1}{k+1}}.$

Δείτε επίσης

• Τρίγωνο του Πασκάλ