Διωνυμικό άθροισμα (ΙΙ)

[Tolaso J Kos]

Έστω . Να υπολογιστεί το .

[Demetres]

Ας παρατηρήσουμε ότι υπάρχουν διαφορετικά μονοπάτια από το στο μέσω του όπου κάθε φορά μετακινούμαστε ένα βήμα δεξιά ή ένα βήμα πάνω.

Επομένως το



μετράει για όλα τα μονοπάτια από το ως το πόσες φορές περάσαμε από ένα από τα σημεία .

Επειδή ακριβώς σε μονοπάτια περνάμε από το θα υπολογίσουμε το το οποίο μετράει πόσες φορές περάσαμε από ένα από τα σημεία .

Πιο γενικά το μετράει για όλα τα μονοπάτια από το ως το πόσες φορές περάσαμε από ένα από τα σημεία .

Θα δείξουμε επαγωγικά ότι επομένως το ζητούμενο άθροισμα θα είναι

Έστω το πρώτο σημείο μετά το στην κύρια διαγώνιο από το οποίο περνάμε. Υπάρχουν τρόπο να πάμε από το στο μένοντας αυστηρά κάτω από τη διαγώνιο (εκτός από το πρώτο και τελευταίο σημείο). Επίσης για να πάμε από το στο επαγωγικά περνάμε φορές από σημεία της κύριας διαγωνίου.

Επομένως αρκεί να δείξουμε ότι



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

Προχωράμε με επαγωγή στο με το να είναι άμεσο. Για το επαγωγικό βήμα παρατηρούμε ότι