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

Συντονιστής: Demetres

Λάμπρος Κατσάπας
Δημοσιεύσεις: 512
Εγγραφή: Σάβ Ιουν 17, 2017 10:17 pm
Τοποθεσία: Αθήνα

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

#1

Μη αναγνωσμένη δημοσίευση από Λάμπρος Κατσάπας » Δευ Ιούλ 01, 2019 12:21 am

Κατά την επίλυση ενός προβλήματος μου προέκυψε η παρακάτω ως δύο ''διαφορετικές'' απαντήσεις στο πρόβλημα οι οποίες

αναγκαστικά είναι ίδιες. Να δείξετε ότι

\displaystyle \binom{n}{k}\sum_{i=0}^{n-k}(-1)^i\frac{\binom{n-k}{i}}{k+i+1}=\frac{1}{n+1},
για κάθε k=0,1,...,n.



Λέξεις Κλειδιά:
sot arm
Δημοσιεύσεις: 182
Εγγραφή: Τρί Μάιος 03, 2016 5:25 pm

Re: Συνδυαστική ταυτότητα

#2

Μη αναγνωσμένη δημοσίευση από sot arm » Δευ Ιούλ 01, 2019 9:49 pm

Λάμπρος Κατσάπας έγραψε:
Δευ Ιούλ 01, 2019 12:21 am
Κατά την επίλυση ενός προβλήματος μου προέκυψε η παρακάτω ως δύο ''διαφορετικές'' απαντήσεις στο πρόβλημα οι οποίες

αναγκαστικά είναι ίδιες. Να δείξετε ότι

\displaystyle \binom{n}{k}\sum_{i=0}^{n-k}(-1)^i\frac{\binom{n-k}{i}}{k+i+1}=\frac{1}{n+1},
για κάθε k=0,1,...,n.
Βάζω μία λύση, από το διωνυμικό έχουμε:

\displaystyle{(\frac{1}{x})^{n}=(1+\frac{1}{x}-1)^{n}=(1+(\frac{1}{x}-1))^{n}= \sum_{k=0}^{n}\binom{n}{k}(\frac{1}{x}-1)^{n-k}= \sum_{k=0}^{n}\binom{n}{k}\sum_{i=0}^{n-k}\binom{n-k}{i}(\frac{1}{x})^{n-k-i}(-1)^{i}\Leftrightarrow}

\displaystyle{1=\sum_{k=0}^{n}\binom{n}{k}\sum_{i=0}^{n-k}\binom{n-k}{i}x^{i+k}(-1)^{i}}

Κοιτώντας τους συντελεστές των θετικών δυνάμεων του x βλέπουμε πως κάθε όρος του πρώτου αθροίσματος είναι ανεξάρτητος του κ, άρα:


\displaystyle{\frac{1}{n+1}=\binom{n}{k}\sum_{i=0}^{n-k}\binom{n-k}{i}(-1)^{i}x^{k+i}}

Αφού το άθροισμα έχει n+1 όρους.

ολοκληρώνοντας την παραπάνω, από 0 έως 1 προκύπτει το ζητούμενο.


Αρμενιάκος Σωτήρης
Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 11477
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: Συνδυαστική ταυτότητα

#3

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Δευ Ιούλ 01, 2019 11:27 pm

Λάμπρος Κατσάπας έγραψε:
Δευ Ιούλ 01, 2019 12:21 am
Να δείξετε ότι

\displaystyle \binom{n}{k}\sum_{i=0}^{n-k}(-1)^i\frac{\binom{n-k}{i}}{k+i+1}=\frac{1}{n+1},
για κάθε k=0,1,...,n.
Αλλιώς (με χρήση απλής ιδιότητας της συνάρτησης Beta).

Θέτουμε \displaystyle f(x)= \binom{n}{k}\sum_{i=0}^{n-k}(-1)^i\dfrac{\binom{n-k}{i}}{k+i+1}x^{k+i+1}, οπότε

\displaystyle f'(x)= \binom{n}{k}\sum_{i=0}^{n-k}(-1)^i\binom{n-k}{i}}x^{k+i}=x^k  \binom{n}{k}\sum_{i=0}^{n-k}(-1)^i\binom{n-k}{i}}x^{i} = x^k  \binom{n}{k}(1-x)^{n-k}

Ολοκληρώνοντας από 0 έως 1 έπεται \displaystyle f(1)-f(0) = \binom{n}{k}\dfrac {\Gamma (k+1) \Gamma (n-k+1)}{\Gamma (k+n-k+2)}= \binom{n}{k}\dfrac {k! (n-k)!}{(n+1)!}= \dfrac{1}{n+1}, όπως θέλαμε.


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8239
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Συνδυαστική ταυτότητα

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Ιούλ 02, 2019 8:44 am

Βάζω μια σύντομη λύση αν και δεν είναι η αρχική μου απόδειξη.

Ισοδύναμα, θέτοντας m = n-k, θέλουμε να δείξουμε ότι

\displaystyle  \sum_{i=0}^m (-1)^i \binom{m}{i} \frac{(k+1)(k+2) \cdots (k+m+1)}{m!(k+i+1)} = 1

το οποίο είναι προφανές (λέμε τώρα) αφού το αριστερό μέλος είναι το πολυώνυμο παρεμβολής Lagrange για τα σημεία (-1,1),(-2,1),\ldots,(-(m+1),1).


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες