Come ormai faccio ogni mese, vi propongo, ora che è scaduto il termine delle consegne, un problema della gara telematica dell'UNIMI. Questa volta però non so la soluzione e non so stimare la difficoltà del problema, anyway:
Provare che:
$ \displaystyle\binom{n}{1}^{-1}+\binom{n}{2}^{-1}+\dots+\binom{n}{n}^{-1} $$ = $ $ \displaystyle\frac{n+1}{2^n}\left({\frac{2^0}{0+1}+\frac{2^1}{1+1}+\frac{2^2}{2+1}+\dots+\frac{2^{n-1}}{n-1+1}\right) $
Sommiamo gli inversi dei binomiali
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
-
JackSparrow
- Messaggi: 22
- Iscritto il: 01 gen 1970, 01:00
:D Ci ho perso tantissimo tempo ad indurre.. E alla fine non mi veniva nulla a parte conti inutili...-
JackSparrow
- Messaggi: 22
- Iscritto il: 01 gen 1970, 01:00
Ecco la mia dimostrazione:
-Passo base: per n = 1 otteniamo $ \displaystyle{1=\frac{1}{1}\frac{2}{2}} $, che è vero
-Passo induttivo: cerchiamo innanzitutto un modo per esprimere $ \displaystyle{\sum_{j=1}^{n+1} \frac{1}{\binom{n+1}{j}}} $ (che chiameremo per semplicità $ x_{n + 1} $) in funzione di $ \displaystyle{\sum_{j=1}^{n} \frac{1}{\binom{n}{j}}} $ (che chiameremo $ x_n $). Scriviamo perciò in forma estesa le due sommatorie, ottenendo $ \displaystyle{x_n=\frac{1!(n-1)!+2!(n-2)!+…+n!0!}{n!}} $ e $ \displaystyle{x_{n+1}=\frac{1!n!+2!(n-1)!+…+(n+1)!}{(n+1)!}} $; eseguiamo ora la differenza $ x_{n+1}(n+1)!-x_nn!=1!n!-(2!-1!)(n-1)!+…+((n+1)!-n!)0! $. Osserviamo ora che, per ogni k intero positivo, si ha $ (k+1)!-k!=k!(k+1-1)=k!k $; possiamo perciò scrivere il risultato sopra ottenuto come $ \displaystyle{1!n!+ n!n + \sum_{i=1}^{n} i!(n-i)!} $ . È ora possibile esprimere la sommatoria centrale (che chiamiamo sn) in funzione di $ x_n $; infatti, se la prendiamo due volte e ne scriviamo i termini una volta in ordine di i crescente, un’altra volta nell’ordine inverso, per poi sommare ogni termine della prima somma con quello che occupa lo stesso posto nella seconda somma, otterremo una serie di somme nella forma $ k!k(n-k)!+(n-k)!(n-k)k! $, che è evidentemente uguale a $ \displaystyle{k!(n-k)!n=n!n\frac{k!(n-k)!}{n!}} $. Osserviamo a questo punto che la somma dei termini $ \displaystyle{\frac{k!(n-k)!}{n!}} $ con k che va da 1 a n – 1 non è altro che la sommatoria che abbiamo precedentemente denotato con $ x_n $, privata dell’ultimo termine (quello in cui k = n, pari a 1); ne segue che la sommatoria sn sarà pari a $ \displaystyle{n!n\frac{x_n-1 }{2}} $. Sostituendo questo valore nel risultato precedentemente calcolato per la differenza $ x_{n + 1}(n + 1)!-x_nn! $ otteniamo $ \displaystyle{x_{n+1}(n+1)!-x_nn!=n!(n+1)+ n!n\frac{x_n-1}{2}} $, da cui vediamo facilmente che $ \displaystyle{x_{n+1}= n!n\frac{(n+2)(x_n-1)}{2(n+1)}} $. Osserviamo a questo punto il secondo membro dell’uguaglianza da dimostrare, che chiameremo $ y_n $ e calcoliamo $ y_{n+1} $ in funzione di $ y_n $. Otteniamo in questo modo $ \displaystyle{y_{n+1}=(y_n+\frac{2^n}{n+1}+\frac{2^n}{n+1})\frac{n+2}{2^{n+2}}=\frac{(y_n-1)(n+2)}{2(n+1)}} $. Osserviamo a questo punto che la relazione che esprime $ x_{n + 1} $ in funzione di $ x_n $ è uguale a quella che esprime $ y_{n + 1} $ in funzione di $ y_n $, per cui, se $ x_n = y_n $, necessariamente si avrà $ x_{n + 1} = y_{n + 1} $. La dimostrazione per induzione è così completa.
-Passo base: per n = 1 otteniamo $ \displaystyle{1=\frac{1}{1}\frac{2}{2}} $, che è vero
-Passo induttivo: cerchiamo innanzitutto un modo per esprimere $ \displaystyle{\sum_{j=1}^{n+1} \frac{1}{\binom{n+1}{j}}} $ (che chiameremo per semplicità $ x_{n + 1} $) in funzione di $ \displaystyle{\sum_{j=1}^{n} \frac{1}{\binom{n}{j}}} $ (che chiameremo $ x_n $). Scriviamo perciò in forma estesa le due sommatorie, ottenendo $ \displaystyle{x_n=\frac{1!(n-1)!+2!(n-2)!+…+n!0!}{n!}} $ e $ \displaystyle{x_{n+1}=\frac{1!n!+2!(n-1)!+…+(n+1)!}{(n+1)!}} $; eseguiamo ora la differenza $ x_{n+1}(n+1)!-x_nn!=1!n!-(2!-1!)(n-1)!+…+((n+1)!-n!)0! $. Osserviamo ora che, per ogni k intero positivo, si ha $ (k+1)!-k!=k!(k+1-1)=k!k $; possiamo perciò scrivere il risultato sopra ottenuto come $ \displaystyle{1!n!+ n!n + \sum_{i=1}^{n} i!(n-i)!} $ . È ora possibile esprimere la sommatoria centrale (che chiamiamo sn) in funzione di $ x_n $; infatti, se la prendiamo due volte e ne scriviamo i termini una volta in ordine di i crescente, un’altra volta nell’ordine inverso, per poi sommare ogni termine della prima somma con quello che occupa lo stesso posto nella seconda somma, otterremo una serie di somme nella forma $ k!k(n-k)!+(n-k)!(n-k)k! $, che è evidentemente uguale a $ \displaystyle{k!(n-k)!n=n!n\frac{k!(n-k)!}{n!}} $. Osserviamo a questo punto che la somma dei termini $ \displaystyle{\frac{k!(n-k)!}{n!}} $ con k che va da 1 a n – 1 non è altro che la sommatoria che abbiamo precedentemente denotato con $ x_n $, privata dell’ultimo termine (quello in cui k = n, pari a 1); ne segue che la sommatoria sn sarà pari a $ \displaystyle{n!n\frac{x_n-1 }{2}} $. Sostituendo questo valore nel risultato precedentemente calcolato per la differenza $ x_{n + 1}(n + 1)!-x_nn! $ otteniamo $ \displaystyle{x_{n+1}(n+1)!-x_nn!=n!(n+1)+ n!n\frac{x_n-1}{2}} $, da cui vediamo facilmente che $ \displaystyle{x_{n+1}= n!n\frac{(n+2)(x_n-1)}{2(n+1)}} $. Osserviamo a questo punto il secondo membro dell’uguaglianza da dimostrare, che chiameremo $ y_n $ e calcoliamo $ y_{n+1} $ in funzione di $ y_n $. Otteniamo in questo modo $ \displaystyle{y_{n+1}=(y_n+\frac{2^n}{n+1}+\frac{2^n}{n+1})\frac{n+2}{2^{n+2}}=\frac{(y_n-1)(n+2)}{2(n+1)}} $. Osserviamo a questo punto che la relazione che esprime $ x_{n + 1} $ in funzione di $ x_n $ è uguale a quella che esprime $ y_{n + 1} $ in funzione di $ y_n $, per cui, se $ x_n = y_n $, necessariamente si avrà $ x_{n + 1} = y_{n + 1} $. La dimostrazione per induzione è così completa.
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
Adesso non mi va di scrivere tutto il procedimento, comunque si basa sul fatto che:
$ \displaystyle \frac {n+2}{n+1} \binom nk ^{-1}=\frac {k+1}{n+1} \binom nk ^{-1}+\frac {n-k+1}{n+1} \binom n{n-k} ^{-1} $$ \displaystyle = \binom {n+1}{k+1} ^{-1} + \binom {n+1}k ^{-1} $
Sommando il tutto con k che va da 0 a n otteniamo:
$ \displaystyle \frac {n+2}{n+1} \sum_{k=0}^n \binom nk ^{-1}= 2 \sum_{k=0}^{n+1} \binom {n+1}k ^{-1} - \binom {n+1}0 ^{-1} - \binom {n+1}{n+1} ^{-1} $
E quindi troviamo la ricorsione voluta $ S_{n+1}= \frac {(n+2)S_n}{2n+2}+1 $. Si vede che anche l'altro membro ha una ricorsione uguale e quindi per induzione si risolve vedendo il caso n=1.
$ \displaystyle \frac {n+2}{n+1} \binom nk ^{-1}=\frac {k+1}{n+1} \binom nk ^{-1}+\frac {n-k+1}{n+1} \binom n{n-k} ^{-1} $$ \displaystyle = \binom {n+1}{k+1} ^{-1} + \binom {n+1}k ^{-1} $
Sommando il tutto con k che va da 0 a n otteniamo:
$ \displaystyle \frac {n+2}{n+1} \sum_{k=0}^n \binom nk ^{-1}= 2 \sum_{k=0}^{n+1} \binom {n+1}k ^{-1} - \binom {n+1}0 ^{-1} - \binom {n+1}{n+1} ^{-1} $
E quindi troviamo la ricorsione voluta $ S_{n+1}= \frac {(n+2)S_n}{2n+2}+1 $. Si vede che anche l'altro membro ha una ricorsione uguale e quindi per induzione si risolve vedendo il caso n=1.
:P