Ταυτότητα με διωνυμικούς συντελεστές!

Συντονιστές: achilleas, emouroukos, silouan

Άβαταρ μέλους
matha
Γενικός Συντονιστής
Δημοσιεύσεις: 6033
Εγγραφή: Παρ Μάιος 21, 2010 7:40 pm
Τοποθεσία: Θεσσαλονίκη

Ταυτότητα με διωνυμικούς συντελεστές!

#1

Μη αναγνωσμένη δημοσίευση από matha » Δευ Δεκ 18, 2017 10:19 am

Ας είναι \displaystyle{n} ένας θετικός ακέραιος. Να αποδειχθεί ότι

\displaystyle{\boxed{\rm{\sum_{j=0}^{n}\binom{n}{j}^{-1}=\frac{n+1}{2^{n+1}}\sum_{j=1}^{n+1}\frac{2^j}{j}}}}


Μάγκος Θάνος

Λέξεις Κλειδιά:
Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 9939
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: Ταυτότητα με διωνυμικούς συντελεστές!

#2

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Τρί Δεκ 26, 2017 6:02 pm

matha έγραψε:
Δευ Δεκ 18, 2017 10:19 am
Ας είναι \displaystyle{n} ένας θετικός ακέραιος. Να αποδειχθεί ότι

\displaystyle{\boxed{\rm{\sum_{j=0}^{n}\binom{n}{j}^{-1}=\frac{n+1}{2^{n+1}}\sum_{j=1}^{n+1}\frac{2^j}{j}}}}
Δύσκολη. Θα την γράψω χωρίς κάποιες επίπονες πράξεις:

Έστω a_n το αριστερό μέλος και b_n το δεξί. Είναι a_0=b_0=1 και a_1=b_1=2. Για να δείξουμε την ζητούμενη ισότητα a_n=b_n
για κάθε n αρκεί να δείξουμε ότι τα (a_n) και, χωριστά, τα (b_n) , ικανοποιούν την ίδια αναδρομική σχέση δύο όρων.

Την αναδρομική σχέση την ανακαλύπτουμε από τα b_n που είναι ευκολότερα. Με χαρτί, μολύβι και πολύ πρόχειρο θα διαπιστώσουμε
ότι ισχύει \displaystyle{\displaystyle { \boxed { 2(n+1)b_{n+1} = (n+2)b_n+2n+2   ,\,(*)}

O έλεγχος είναι εύκολος αλλά η δυσκολία είναι στην ανακάλυψή του. Εδώ, από τον ορισμό των b_n έχουμε

\displaystyle{ 2(n+1)b_{n+1} = 2(n+1)\frac{n+2}{2^{n+2}}\sum_{j=1}^{n+2}\frac{2^j}{j}=  2(n+1)\frac{n+2}{2^{n+2}} \left (\sum_{j=1}^{n+1}\frac{2^j}{j}+ \frac{2^{n+2}}{n+2}   \right ) }

\displaystyle{ =  2(n+1)\frac{n+2}{2^{n+2}} \left ( \frac{2^{n+1}}{n+1}   b_n   + \frac{2^{n+2}}{n+2}   \right ) = (n+2)b_n+2(n+1)} όπως θέλαμε.

Για τα a_n από τις ταυτότητες \displaystyle{ \binom{n+1}{j}= \binom{n}{j}\frac {n+1}{n+1-k}} και \displaystyle{ \binom{n}{j+1}= \binom{n}{j}\frac {n-j}{k+1}}

εύκολα βλέπουμε ότι ισχύει η

\displaystyle{ \frac {2(n+1)}{ \binom{n+1}{j}  }  = \frac {n+2}{ \binom{n}{j}  }  + \frac {n+1-j}{ \binom{n}{j}  } - \frac {n-j}{ \binom{n}{j+1}  } }

Προσθέτοντας κατά μέλη από 0 έως n-1 τηλεσκοπικά θα βρούμε

\displaystyle{2(n+1)\left (a_{n+1} -1 - \frac {1}{n+1} \right)  = (n+2) (a_n-1) + n } και άρα

\displaystyle{2(n+1)a_{n+1} = (n+2)a_n+2n+2} που είναι ίδια με την (*) και με ίδιες αρχικές συνθήκες. Και λοιπά.


Άβαταρ μέλους
Tolaso J Kos
Δημοσιεύσεις: 3158
Εγγραφή: Κυρ Αύγ 05, 2012 10:09 pm
Τοποθεσία: Λάρισα
Επικοινωνία:

Re: Ταυτότητα με διωνυμικούς συντελεστές!

#3

Μη αναγνωσμένη δημοσίευση από Tolaso J Kos » Τρί Δεκ 26, 2017 7:35 pm

Γνώριζα την απάντηση και δεν έδωσα λύση μιας και η πληκτρολόγηση είναι εκτενής. Ο πρώτος που απέδειξε αυτή τη ταυτότητα είναι ο Staver ( 1947 ) ο οποίος ορίζοντας \displaystyle{S_n^{(m)}= \sum_{k=0}^{n} k^m \binom{n}{k}^{-1} } παρατήρησε ότι  \displaystyle S^{(1)}_n = \frac{n}{2} S^{(0)}_n και με βάση αυτό έβγαλε τον αναγωγικό τύπο:
\displaystyle{S_{n+1}^{(0)} = \frac{n+2}{2(n+1)} S_n^{(0)} +1 \quad \quad\quad (1)} και απέδειξε τη παραπάνω σχέση. Το 1993 ο Sury έδωσε απόδειξη της ταυτότητας με τη χρήση της ολοκληρωτικής αναπαράστασης του διωνυμικού συντελεστή,

\displaystyle{\binom{n}{k}^{-1} = (n+1)\int_{0}^{1} x^k \left ( 1-x \right )^{n-k} \, {\rm d}x \quad \quad \quad (2) }
ενώ νωρίτερα το 1981 ο Rocket χρησιμοποιώντας επαγωγή και τη ταυτότητα \displaystyle{\binom{n}{k}^{-1} = \binom{n-1}{k-1}^{-1}  - \frac{n-k}{n-k+1} \binom{n}{k-1}^{-1}} απέδειξε την ταυτότητα. Έκτοτε έχουν μελετηθεί εκτενώς οι περιπτώσεις m=0 \;, \;m=1. Μερικά χρόνια αργότερα ο Mansour γενίκευσε την ιδέα του Sury και απέδειξε το παρακάτω θεώρημα:

Θεώρημα [Mansour] Έστω r, n \geq k μη αρνητικοί ακέραιοι αριθμοί και f(n, k) η οποία ορίζεται ως

\displaystyle{f(n, k) = \frac{(n+r)!}{n!} \int_{u_1}^{u_2} p^k(t) q^{n-k}(t) \, {\rm d}t}
όπου p, q δύο συναρτήσεις ορισμένες στο διάστημα [u_1 u_2]. Έστω \{a_n\}_{n \in \mathbb{N}} , \{b_n\}_{n \in \mathbb{N}} δύο ακολουθίες και έστω A(x), B(x) οι αντίστοιχες γεννήτριες συναρτήσεις. Τότε:

\displaystyle{\sum_{n=0}^{\infty} \left ( \sum_{k=0}^{n} f(n, k) a_k b_{n-k} \right ) x^n = \frac{\mathrm{d}^r}{\mathrm{d} x^r} \left ( x^r \int_{u_1}^{u_2} A\left ( xp(t) \right ) B(xq(t))\, {\rm d}t \right ) }
Από το παραπάνω θεώρημα και χρησιμοποιώντας τη (2) παίρνουμε με κατάλληλες επιλογές υπέροχα πράγματα. Για παράδειγμα:

Παράδειγμα: Αν a_n=a^n και b_n=b^n τότε:
\displaystyle{\begin{aligned} 
\sum_{n=0}^{\infty} \left ( \sum_{k=0}^{n} a^k b^{n-k} \binom{n}{k}^{-1} \right )x^n &= \frac{\mathrm{d} }{\mathrm{d} x} \left ( x \int_{0}^{1} \frac{{\rm d}t}{\left ( 1-axt \right )\left ( 1-bx+bxt \right )} \right )   \\  
 &= \frac{\mathrm{d} }{\mathrm{d} x} \left ( \frac{-\log (1-ax)-\log(1-bx)}{a+b-abx} \right ) 
\end{aligned}} και μετά από κάποιους μετασχηματισμούς παίρνουμε το γενικότερο:

\displaystyle{\boxed{\sum_{k=0}^{n}a^n b^{n-k} \binom{n}{k}^{-1} =\frac{n+1}{\left ( a+b \right )\left ( \frac{1}{a}+\frac{1}{b} \right )^{n+1}} \sum_{k=1}^{n+1} \frac{\left ( a^k+b^k \right )\left ( \frac{1}{a}+ \frac{1}{b} \right )^{k}}{k}}}
Για a=b=1 παίρνουμε τη ζητούμενη. Αν από την άλλη θέσουμε a_n=n και b_n=1 τότε παίρνουμε:

\displaystyle{\boxed{\sum_{k=0}^{n} k \binom{n}{k}^{-1} = \frac{1}{2^n} \left [ (n+1) \left ( 2^n-1 \right ) +\sum_{k=0}^{n-2} \frac{\left ( n-k \right )\left ( n-k-1 \right )2^{k-1}}{k+1} \right ]}}
Υ.Σ 1: Η απόδειξη του θεωρήματος είναι "τυπική" και γίνεται με γεννήτριες.

Υ.Σ 2: Το θεώρημα δίδει , επίσης , καταπληκτικές εφαρμογές.

Υ.Σ 3: Ξέφυγα από το φάκελο , αλλά δε πειράζει.


Η φαντασία είναι σημαντικότερη από τη γνώση !
\displaystyle{{\color{blue}\mathbf{Life=\int_{birth}^{death}\frac{happiness}{time}\Delta time} }}
Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 9939
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: Ταυτότητα με διωνυμικούς συντελεστές!

#4

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Τρί Δεκ 26, 2017 8:37 pm

Τόλη, καταπληκτικά αυτά που μας γράφεις. :clap:


Άβαταρ μέλους
Tolaso J Kos
Δημοσιεύσεις: 3158
Εγγραφή: Κυρ Αύγ 05, 2012 10:09 pm
Τοποθεσία: Λάρισα
Επικοινωνία:

Re: Ταυτότητα με διωνυμικούς συντελεστές!

#5

Μη αναγνωσμένη δημοσίευση από Tolaso J Kos » Τρί Δεκ 26, 2017 10:36 pm

Και για μελλοντική αναφορά δίνω και τη παρακάτω:

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


Η φαντασία είναι σημαντικότερη από τη γνώση !
\displaystyle{{\color{blue}\mathbf{Life=\int_{birth}^{death}\frac{happiness}{time}\Delta time} }}
achilleas
Επιμελητής
Δημοσιεύσεις: 2528
Εγγραφή: Τρί Σεπ 15, 2009 3:32 pm

Re: Ταυτότητα με διωνυμικούς συντελεστές!

#6

Μη αναγνωσμένη δημοσίευση από achilleas » Τρί Δεκ 26, 2017 10:47 pm

matha έγραψε:
Δευ Δεκ 18, 2017 10:19 am
Ας είναι \displaystyle{n} ένας θετικός ακέραιος. Να αποδειχθεί ότι

\displaystyle{\boxed{\rm{\sum_{j=0}^{n}\binom{n}{j}^{-1}=\frac{n+1}{2^{n+1}}\sum_{j=1}^{n+1}\frac{2^j}{j}}}}
Το πρόβλημα αυτό μας θυμίζει το Β1 του Putnam του 1958.

Σχεδόν ίδιο είναι το πρόβλημα 1682 που προτάθηκε στο Mathematics Magazine.

Το Δεκέμβρη του 2004, το Mathematics Magazine δημοσίευσε δύο λύσεις και στα σχόλια δίνει 2-3 παραπομπές.

Η ακόλουθη λύση στο ΜΜ1682 που είχα στείλει είναι παρόμοια με τη λύση του κ. Μιχάλη.

Λύση στο ΜΜ1682

Αν L_n είναι το αριστερό μέλος και R_n το δεξί τότε εύκολα βλέπουμε ότι L_1=R_1=1 και

\displaystyle{ 
R_{n+1}=\dfrac{n+2}{2^{n+1}} \left(\sum_{j=0}^{n-1} \dfrac{2^j}{j+1}+ 
\dfrac{2^n}{n+1}\right)=\dfrac{n+2}{2^{n+1}} 
\left(\dfrac{2^{n}R_n}{n+1}+ 
\dfrac{2^n}{n+1}\right)=\dfrac{n+2}{2(n+1)}(R_n +1) 
  }

για καθε n \geq 1, οπότε αρκεί να δείξουμε ότι

\displaystyle{ 
    L_{n+1}=\dfrac{n+2}{2(n+1)}(L_n +1)       (*) 
}

για καθε n \geq 1. Πράγματι, παρατηρούμε ότι

\displaystyle{ 
  \dfrac{1}{{n+1 \choose j}}+\dfrac{1}{{n+1 \choose j+1}}=\dfrac{n+2}{n+1}\cdot \dfrac{1}{{n \choose j}} 
}

για καθε n \geq j \geq 1. Αθροίζοντας τις σχέσεις αυτές για j=1,2,...,n, παίρνουμε

\displaystyle{ 
  \sum_{j=1}^{n} \dfrac{1}{{n+1 \choose j}}+\sum_{j=1}^{n} \dfrac{1}{{n+1 \choose j+1}}=\dfrac{n+2}{n+1}\cdot \sum_{j=1}^{n}\dfrac{1}{{n \choose 
  j}}; 
}

δηλαδή,

\displaystyle{ 
   (L_{n+1}-1)+(L_{n+1}-\dfrac{1}{n+1})=\dfrac{n+2}{n+1}L_n, 
}

από την οποία έπεται η σχέση (*) για την L_{n+1}.

Φιλικά,

Αχιλλέας


Απάντηση

Επιστροφή σε “Άλγεβρα - Προχωρημένο Επίπεδο (Seniors)”

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

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