Sommiamo gli inversi dei binomiali

Polinomi, disuguaglianze, numeri complessi, ...
Rispondi
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Sommiamo gli inversi dei binomiali

Messaggio da Boll » 10 mar 2005, 19:13

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) $

Simo_the_wolf
Moderatore
Messaggi: 1052
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf » 12 mar 2005, 20:31

Direi di trovare una simpatica ricorsione per il membro di sinistra...

JackSparrow
Messaggi: 22
Iscritto il: 01 gen 1970, 01:00

Messaggio da JackSparrow » 26 mar 2005, 19:25

Io l'ho risolto per induzione; la soluzione richiede un bel po' di calcoli, ma funziona.
Se volete la posto, ma prima dovrei imparare ad usare LaTex.

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 26 mar 2005, 19:35

Sì, decisamente la vorrei :D: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

Messaggio da JackSparrow » 28 mar 2005, 18:47

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.

Simo_the_wolf
Moderatore
Messaggi: 1052
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf » 29 mar 2005, 17:45

Ho provato 2 volte a postarla quella maledetta ricorsione ma non vuole farsi vedere... Cmq sta anche sull'Engel, mi pare

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 29 mar 2005, 20:03

In che senso non si vuol far vedere??? Forse devi spezzarla, metti chiudi e riapri il TeX ad un certo punto...

Simo_the_wolf
Moderatore
Messaggi: 1052
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf » 30 mar 2005, 23:11

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.

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 31 mar 2005, 17:39

Molto bella come soluzione, Simo, sulle identità sui binomiali sono scarsissimo... Ancora più che nel resto... :D:D:D Avevo tentato una soluzione tipo quella di JackSparrow, ma dopo che, insieme a MASSO, avevo fatto 4 volte i conti, ho buttato dentro :P:P

Rispondi