Μάζεμα αθροίσματος με δυωνυμικά

Συντονιστές: cretanman, Demetres, polysot, achilleas, socrates, silouan

Άβαταρ μέλους
Κοτρώνης Αναστάσιος
Επιμελητής
Δημοσιεύσεις: 3203
Εγγραφή: Κυρ Φεβ 22, 2009 11:11 pm
Τοποθεσία: Μπροστά στο πισί...
Επικοινωνία:

Μάζεμα αθροίσματος με δυωνυμικά

#1

Μη αναγνωσμένη δημοσίευση από Κοτρώνης Αναστάσιος » Παρ Δεκ 10, 2010 1:03 am

Δεν ξέρω αν είναι ο κατάλληλος φάκελος. Αν χρειαστεί, ας μετακινηθεί.

Συνεχίζοντας από εδώ

Δείξτε ότι

\displaystyle{\boxed{\sum_{k=1}^{n}(-1)^{k+1}\binom{2n+1}{k}(2n-2k+1)^{2j+1}=(2n+1)^{2j+1}}} για \displaystyle{j=0,\ldots,n-1}.


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

Re: Μάζεμα αθροίσματος με δυωνυμικά

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Δεκ 12, 2010 5:40 pm

Απόδειξη 1η (Σκιαγράφηση)

Προχωράμε "επαγωγικά". Το βάζω σε εισαγωγικά διότι θέλει λίγη προσοχή. Το επαγωγικό βήμα (απλό αλλά με αρκετές πράξεις) δείχνει ότι αν η ισότητα ισχύει για το ζεύγος (n,j), τότε ισχύει και για το ζεύγος (n+1,j+1). Είναι προφανές ότι η ισότητα ισχύει για τα ζεύγη (1,0),(2,0),(3,0),\ldots. Άρα ισχύει και για τα ζεύγη (2,1),(3,1),(4,1),\ldots και για τα ζεύγη (3,2),(4,2),(5,2),\ldots κ.τ.λ. Επαγωγικά ισχύει για όλα τα ζεύγη (n,j) με 0 \leqslant j < n.

Απόδειξη 2η:

Παρατηρούμε ότι το ζητούμενο είναι ισοδύναμο με \displaystyle{ \sum_{k=0}^n (-1)^k \binom{2n+1}{k} (2n+1-2k)^{2j+1} = 0}.

Έστω \displaystyle{a_k = (-1)^k \binom{2n+1}{k} (2n+1-2k)^{2j+1}}. Τότε για k+\ell = 2n+1 παρατηρώ ότι a_k = a_{\ell} (εδώ χρησιμοποιώ ότι ο 2j+1 είναι περιττός). Άρα αρκεί να δείξω ότι \displaystyle{ \sum_{k=0}^{2n+1} a_k = 0}.

Αρκεί να δείξω ότι \displaystyle{ \sum_{k=0}^{m} (-1)^k \binom{m}{k}k^r = 0} για κάθε 0 \leqslant r \leqslant m-1. (Παίρνουμε m=2n+1 και παρατηρούμε ότι το (2n+1-2k)^{2j+1} είναι πολυώνυμο του k βαθμού το πολύ m-1.)

Θα δώσω δυο αποδείξεις για το τελευταίο.

Απόδειξη Α: Αρκεί να δείξω ότι \displaystyle{ \sum_{k=0}^{m} (-1)^k \binom{m}{k} \binom{k}{r} = 0} για κάθε 0 \leqslant r \leqslant m-1. (Μετά γράφω το k^r σαν άθροισμα των διωνυμικών συντελεστών \displaystyle{ \binom{k}{1},\ldots, \binom{k}{r}.}). Όμως

\displaystyle{ \sum_{k=0}^{m} (-1)^k \binom{m}{k} \binom{k}{r} = \sum_{k=r}^{m} (-1)^k \binom{m}{k} \binom{k}{r} = \sum_{k=r}^{m} (-1)^k \binom{m}{r} \binom{m-r}{k-r} }

\displaystyle{= (-1)^r\binom{m}{r} \sum_{\ell = 0}^{m-r} (-1)^{\ell} \binom{m-r}{\ell} = (-1)^r \binom{m}{r} (1-1)^{m-r} = 0 }

Απόδειξη Β:

Ο αριθμός των επί συναρτήσεων \{1,\ldots,r\} \to \{1,\ldots,m\} είναι προφανώς 0. Θα τις μετρήσουμε χρησιμοποιώντας το θεώρημα εγκλεισμού-αποκλεισμού. Για i \in \{1,\ldots,m\} θα γράψω A_i για το σύνολο όλων των συναρτήσεων από το \{1,\ldots,r\} στο \{1,\ldots,m\} \setminus \{i\} και A για το σύνολο όλων των συναρτήσεων από το \{1,\ldots,r\} στο \{1,\ldots,m\}. Γνωρίζουμε λοιπόν ότι |A \setminus (A_1 \cup \cdots \cup A_m)| = 0. Όμως από το θεώρημα εγκλεισμού-αποκλεισμού έχουμε

\displaystyle{ |A \setminus (A_1 \cup \cdots \cup A_m)| = \sum_{I \subseteq \{1,\ldots,m\}}(-1)^{|I|} \left| \bigcap_{i \in I} A_i \right| = \sum_{k=0}^{\infty} (-1)^k \binom{m}{k} (m-k)^r = (-1)^m\sum_{k=0}^{\infty} (-1)^k \binom{m}{k} k^r } αφού αν |I| = k τότε ο αριθμός των συναρτήσεων που ανήκουν σε όλα τα A_i με i \in I είναι (m-k)^r


Άβαταρ μέλους
Κοτρώνης Αναστάσιος
Επιμελητής
Δημοσιεύσεις: 3203
Εγγραφή: Κυρ Φεβ 22, 2009 11:11 pm
Τοποθεσία: Μπροστά στο πισί...
Επικοινωνία:

Re: Μάζεμα αθροίσματος με δυωνυμικά

#3

Μη αναγνωσμένη δημοσίευση από Κοτρώνης Αναστάσιος » Τρί Μαρ 27, 2012 8:21 pm

Demetres έγραψε:Αρκεί να δείξω ότι \displaystyle{ \sum_{k=0}^{m} (-1)^k \binom{m}{k}k^r = 0} για κάθε 0 \leqslant r \leqslant m-1...

Θα δώσω δυο αποδείξεις για το τελευταίο.

Απόδειξη Α: ...
Απόδειξη Β: ...

Απόδειξη Γ: (Την είδα κάπου σαν ενδιάμεσο αποτέλεσμα. Οφείλεται στον David Borwein. Εντελώς διαολεμένη...)

Είναι \displaystyle{\sum_{k=0}^{m} (-1)^k \binom{m}{k}k^r =\sum_{k=0}^{m} (-1)^k \binom{m}{k}k^r e^{kx}\Bigg|_{x=0}=\frac{\partial^r}{\partial x^r}(1-e^x)^m\Big|_{x=0}}.

Όμως \displaystyle{(1-e^x)^m=\left(1-\left(1+x+\mathcal O(x^2)\right)\right)^m=(-x)^m+\mathcal O(x^{m+1})}, που σημαίνει ότι \displaystyle{\frac{\partial^r}{\partial x^r}(1-e^x)^m\Big|_{x=0}=0} για 0\leq r<m.


Εσύ....; Θα γίνεις κανίβαλος....;
Απάντηση

Επιστροφή σε “Άλγεβρα - Θεωρία Αριθμών - Συνδυαστική (Seniors) - Παλαιότερες Συζητήσεις”

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

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