Energy Engineering - Analisi e geometria 1

Formula di Newton

Divided by topic

FORMULA DEL BINOMIO DI NEWTON Premessa ∀ n ∈ N definiamo fattoriale di n il numero n ! = 1 ⋅ 2 ⋅ 3  ( n − 1 ) ⋅ n Assumeremo altresì, convenzionalmente, 0 ! = 1 . Diremo inoltre coefficiente binomiale il numero n k ( ) : = n ! k ! ( n − k ) ! questo per ogni k ∈ N tale che 0 ≤ k ≤ n . TEOREMA a + b ( ) n = n k ( ) a n − k b k k = 0 n ∑ per ogni a , b ∈ R . DIMOSTRAZIONE La formula è senz’altro vera (con le co nvenzioni notazionali adottate) per n = 0 e n = 1 , come subito si verifica senza difficoltà. Supponiamo sia vera per un generico n = m ∈ N (ipotesi di induzione); avremo: a + b ( ) m + 1 = a + b ( ) a + b ( ) m = a + b ( ) m k ( ) a m − k b k k = 0 m ∑ = m k ( ) a m + 1 − k b k k = 0 m ∑ + m k ( ) a m − k b k + 1 k = 0 m ∑ = a m + 1 + m k ( ) a m + 1 − k b k k = 1 m ∑ + m k ( ) a m − k b k + 1 k = 0 m − 1 ∑ + b m + 1 Al fine di rendere facilmente riconoscibili i monomi simili delle ultime due sommatorie conviene assumere j = k nella prima e j = k + 1 nella seconda. Così facendo avremo infatti a + b ( ) m + 1 = a m + 1 + m j ( ) a m + 1 − j b j j = 1 m ∑ + m j − 1 ( ) a m + 1 − j b j j = 1 m ∑ + b m + 1 = a m + 1 + m j ( ) + m j − 1 ( ) ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ a m + 1 − j b j j = 1 m ∑ + b m + 1 = a m + 1 + m ! j ! ( m − j ) ! + m ! ( j − 1 ) ! ( m − j + 1 ) ! ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ a m + 1 − j b j j = 1 m ∑ + b m + 1 = a m + 1 + m ! ( m − j + 1 ) + j j ! ( m − j + 1 ) ! a m + 1 − j b j j = 1 m ∑ + b m + 1 = a m + 1 + ( m + 1 ) ! j ! ( m − j + 1 ) ! a m + 1 − j b j j = 1 m ∑ + b m + 1 = m + 1 j ( ) a m − k b k j = 0 m + 1 ∑ In altri termini la formula di Newton vale per n = m + 1 . Conclusione: essa vale con ogni esponente n ∈ N . NUMERO DEI SOTTOINSIEMI DI UN INSIEME FINITO TEOREMA Se A è un insieme finito qualsiasi e ! ( A ) è l’insieme dei suoi sottoinsiemi (propri e non). Posto # ( A ) = n avremo # ( ! ( A ) ) = 2 n . DIMOSTRAZIONE 1 Sia n = 0 ; in tal caso A = ∅ quindi l’unico suo sottoinsieme è ∅ stesso. Si rammenti a questo proposito che ∅ ⊆ B per qualsiasi insieme B . In effetti ∅ ⊆ B è falso solo se esiste un oggetto x ∈ ∅ non appartenente a B , cosa questa senz’altro falsa, essendo ∅ privo di elementi. Conclusione: #( ! ( ∅ ) ) = 1 = 2 0 ; l’enunciato è vero per n = 0 . Supponiamo ora che esso sia vero per n = m > 0 (ipotesi di induzione). Se # ( A ) = m + 1 fissiamo un x ∈ A . Posto ′ A = A − { x } abbiamo # ( ′ A ) = m . È evidente che dato un qualsiasi B ∈ ! ( A ) due sono le possibili alternative: x ∉ B o x ∈ B . Nel primo caso B ⊆ ′ A ; il numero di tali insiemi è – per l’ipotesi di induzione – 2 m . Nel secondo caso B = ( B ∩ ′ A ) ∪ { x } e il numero dei sottoinsiemi B ∩ ′ A è (sempre per l’ipotesi di induzione) 2 m . 1 Se ne trae che # ( ! ( A ) ) = 2 m + 2 m = 2 m + 1 . In altri termini, se la la formula dell’enunciato vale per n = m allora vale per n = m + 1 . Conclusione: essa vale per ogni n ∈ N . DIMOSTRAZIONE 2 Per ogni B ∈ ! ( A ) δ B ( x ) = 1 s e x ∈ B 0 s e x ∈ A − B ⎧ ⎨ ⎪ ⎪ ⎩ ⎪ ⎪ La δ B : A → { 0 , 1 } così definita prende il nome di funzione caratteristica di B . Chiaramente le funzioni δ B sono in corrispondenza biunivoca con i sottoinsiemi di A . Esse possono rappresentarsi con tabulazioni del tipo x 1 x 2  x n δ 1 j 1 δ 2 j 2  δ n j n ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ove x 1 , x 2 , … , x n sono (tutti) gli elementi di A e δ 1 j 1 , δ 2 j 2 , … , δ n j n numeri passibili di assumere i valori 0 o 1. 1 Si noti che sussite la corrispondenza biunivoca ( B ∩ ′ A ) ∪ { x }  B ∩ ′ A . x • A Il numero delle funzioni caratteristiche – ossia # ( ! ( A ) ) – diventa così pari al numero delle disposizioni di 0 e di 1 della seconda riga e quest’ultimo è 2 n , essendoci due opzioni per ognuna delle n posizioni. DISUGUAGLIANZA DI BERNOULLI TEOREMA Se a > − 1 e n ∈ N allora 1 + a ( ) n ≥ 1 + n a DIMOSTRAZIONE La diseguaglianza è senz’altro vera per n = 0 . Supponiamo sia tale per n = m (ipotesi di induzione). Essendo 1 + a > 0 e sfruttando l’ipotesi di induzione abbiamo 1 + a ( ) m + 1 = 1 + a ( ) 1 + a ( ) m ≥ 1 + a ( ) 1 + m a ( ) = 1 + ( m + 1 ) a + m a 2 ≥ 1 + ( m + 1 ) a La disuguaglianza risulta dunque vera per n = m + 1 . Riepilogando: è vera sempre!