4.3 Το Διωνυμικό Θεώρημα

Το Διωνυμικό Θεώρημα (Θεώρημα 4.4 είναι ένα ισχυρότατο εργαλείο για υπολογισμούς που αναφέρονται σε ποσότητες με διωνυμικούς συντελεστές. Είναι επίσης η πρώτη σύνδεση των συνδυαστικών ποσοτήτων που συναντάμε με αλγεβρικές μεθόδους. Αργότερα θα δούμε και τις γεννήτριες συναρτήσεις ακολουθιών σα μια φυσική επέκταση της μεθόδου.

Θεώρημα 4.4   Για κάθε $a,b \in {\mathbb{R}}$, και ακέραιο $n \ge 0$ ισχύει

$$(a+b)^n = \sum_{k=0}^n {n \choose k} a^k b^{n-k}.$$ (4.5)

Απόδειξη. Το αριστερό μέλος είναι ένα γινόμενο $n$ παραγόντων ίσων με $(a+b)$. Όταν κάνουμε όλες τις πράξεις, όταν δηλ. εφαρμόσουμε την επιμεριστική ιδιότητα, αυτό που κάνουμε είναι ότι σχηματίζουμε όλα τα γινόμενα που μπορούμε να φτιάξουμε διαλέγοντας ένα προσθετέο από κάθε παράγοντα (δείτε και Παράδειγμα 3.7) και τα προσθέτουμε, μαζεύοντας μαζί ίδια μονώνυμα.

Είναι φανερό ότι, εφόσον οι προσθετέοι από κάθε παράδειγμα είναι $a$ ή $b$ και το πλήθος των παραγόντων είναι $n$, όλα τα μονώνυμα που θα εμφανιστούν είναι της μορφής

$$a^k b^{n-k}, (0 \le k \le n).$$

Το μονώνυμο αυτό εμφανίζεται οποτεδήποτε έχουμε επιλέξει το $a$ από ακριβώς $k$ από τους παράγοντες. Αλλά αυτό συμβαίνει με ακριβώς τόσους τρόπους όσοι είναι οι τρόποι να επιλεγούν $k$ παράγοντες από τους $n$, δηλ. ${n \choose k}$, και αυτό ακριβώς είναι το περιεχόμενο του θεωρήματος. $\qedsymbol$

Άσκηση 4.14   Ποιο είναι το ανάπτυγμα του $(1+x)^5$ σε δυνάμεις του $x$;

Το Διωνυμικό Θεώρημα (Θεώρημα 4.4) έχει πολλές εφαρμογές σε υπολογισμούς αθροισμάτων.

Παράδειγμα 4.4   Θέτοντας $a=b=1$ στην (4.5) παίρνουμε την ταυτότητα (δείτε και την Άσκηση 3.36)

$$2^n = \sum_{k=0}^n {n \choose k}.$$

Παράδειγμα 4.5   Θέτοντας $a=1, b=-1$ στην (4.5) και χωρίζοντας τους αρνητικούς από τους θετικούς όρους παίρνουμε ότι για κάθε $n$ το άθροισμα των διωνυμικών συντελεστών ${n \choose k}$ για $k$ άρτιο είναι ίσο με το άθροισμα για $k$ περιττό

$$\sum_{0\le k \le n \atop {k \pi\epsilon\rho\iota\tau\tau o}} {n \choose k} = \sum_{0\le k \le n \atop {k \alpha\rho\tau\iota o}} {n \choose k}.$$ (4.6)

Αυτό είναι φανερό όταν το $n$ είναι περιττό, μια και τότε οι διωνυμικοί συντελεστές με άρτιο $k$ βρίσκονται σε ένα προς ένα αντιστοιχία με τους συντελεστές με περιττό $k$ (αφού ισχύει πάντα ${n \choose k} = {n \choose n-k}$-δείτε και Άσκηση 3.37), αλλά δεν είναι εξίσου εύκολο για άρτιο $k$.

Παράδειγμα 4.6   Θέτουμε $a=x, b=1$ στην (4.5) και παραγωγίζουμε τη σχέση που προκύπτει ως προς $x$. Παίρνουμε έτσι

$$n(1+x)^{n-1} = \sum_{k=1}^n k{n \choose k} x^{k-1}.$$

Θέτοντας τώρα $x=1$ παίρνουμε τη σχέση

$$\sum_{k=1}^n k{n \choose k} = n 2^{n-1}.$$

Άσκηση 4.15   Υπολογίστε το άθροισμα $\sum_{k=0}^n 2^k {n \choose k}$.

Άσκηση 4.16   Υπολογίστε το άθροισμα $\sum_{k=2}^n k(k-1) {n \choose k}$.

Άσκηση 4.17   Έστω ότι έχουμε δύο συναρτήσεις

$$a(x) = a_{-N} x^{-N} + a_{-N+1}x^{-N+1}+\cdots+a_0+a_1 x+ \cdots a_N x^N$$

και

$$b(x) = b_{-N} x^{-N} + b_{-N+1}x^{-N+1}+\cdots+b_0+b_1 x+ \cdots b_N x^N$$

όπου τα $a_j$ και $b_j$ είναι πραγματικοί αριθμοί. Μια τέτοια συνάρτηση (δεν ορίζεται στο 0) ονομάζεται πολυώνυμο Laurent και η διαφορά του από τα συνήθη πολυώνυμα είναι ότι έχουμε και αρνητικούς εκθέτες. Αποδεικνύεται ότι οι συντελεστές $a_j$ καθορίζονται από τη συνάρτηση $a(x)$, δε μπορεί δηλ. η ίδια συνάρτηση να γραφτεί με διαφορετικούς συντελεστές.

Αν γράψουμε $c(x) = a(x)b(x)$ δείξτε ότι και η συνάρτηση $c(x)$ είναι πολυώνυμο Laurent και ότι οι συντελεστές της δίνονται από τον τύπο

$$c_s = \sum_{\max{\left\{{-N, s-N}\right\}}}^{\min{\left\{{N, N-s}\right\}}} a_k b_{s-k},$$

για $-2N \le s \le 2N$.

Άσκηση 4.18   Θέτοντας $a=x, b=1/x$ και $2n$ στη θέση του $n$ στην (4.5) δείξτε την ταυτότητα

$${2n \choose n} = \sum_{k=0}^n {n \choose k}^2,$$

εξετάζοντας το συντελεστή του σταθερού όρου και χρησιμοποιώντας και την Άσκηση 4.17.

Άσκηση 4.19   Ποιος ο συντελεστής του $x^3y^5$ στο ανάπτυγμα του $(1+x+y)^{12}$; Εκφράστε την απάντησή σας με πολυωνυμικούς συντελεστές. (Δείτε την §4.2.)

Παράδειγμα 4.7   Σε αυτό το παράδειγμα υπολογίζουμε το άθροισμα

$$\sum_{k=0}^n \frac{1}{k+1} {n \choose k}.$$

Και πάλι χρησιμοποιούμε το διωνυμικό θεώρημα. Κατ' αναλογία με το Παράδειγμα 4.6 στο οποίο παραγωγίσαμε ως προς $x$ το διωνυμικό θεώρημα στη μορφή

$$(1+x)^n = \sum_{k=0}^n {n \choose k} x^k$$

ώστε να εμφανίσουμε ένα παράγοντα $k$ μπροστά από το διωνυμικό συντελεστή ${n \choose k}$ στο δεξί μέλος, εδώ θέλουμε να εμφανίσουμε ένα παράγοντα $1/(k+1)$ οπότε το φυσιολογικό είναι να ολοκληρώσουμε. Έστω λοιπόν

$$f(x) = \sum_{k=0}^n \frac{1}{k+1} {n \choose k} x^k.$$

Εμάς μας ενδιαφέρει να βρούμε το $f(1)$ αλλά θα βρούμε τελικά ένα τύπο για τη συνάρτηση $f(x)$ πριν θέσουμε $x=1$. Πολλαπλασιάζουμε την προηγούμενη ισότητα με $x$ και έπειτα την παραγωγίζουμε ως προς $x$ για να πάρουμε

$$(x f(x))' = \sum_{k=0}^n {n \choose k} x^k = (1+x)^n$$

από την οποία, με ολοκλήρωση, προκύπτει ότι υπάρχει μια σταθερά $C$ τέτοια ώστε

$$x f(x) = \int (1+x)^n dx + C$$

ή

$$x f(x) = \frac{(1+x)^{n+1}}{n+1} + C.$$

Θέτοντας $x=0$ προκύπτει ότι $C=-1/(n+1)$ οπότε

$$x f(x) = \frac{(1+x)^{n+1} - 1}{n+1}$$

και με $x=1$ παίρνουμε $f(1)=\frac{2^n-1}{n+1}$