#E3 – #A10: P(n-1)+ è la stessa cosa + P(n+1)


Qui sono esemplificati i due metodi induttivi (induzione ed induzione forte) 

  • (A): P(n-1)+P(n) = P(n)
  • (B): P(n) + P(n+1) = P(n+1)
  • grigio + verde = Ipotesi = Tesi

2018-09-28_11-38-54_595.jpg

#A11 -E2: Induzione Geometrica


un esempio facile di metodo di induzione visto dal punto di vista geometrico.

Si ha il seguente enunciato: Dimostrare che la somma degli angoli interni di un poligono di n lati equivale a (n-2)*180° angoli piatti. 

Riscriviamo la Proposizione P meglio:

  • P(n) = la somma degli angoli interni di un triangolo di n lati 
  • (n-2)*180 = angoli piatti

quindi abbiamo che P(n) = (n-2)*180 

  1. troviamo se P(0) è vera
    Se pensiamo al quadrato, come poligono di 4 lati e sostituiamo la n col 4 avremo
    (4-2)*180° = 2*180° = 360°
    Stessa cosa col pentagono, n = 5 avremo (5-2)*180 = 540° … ecc quindi banalmente per ogni sostituzione di n P(n) è sempre vera.
  2. Se P(n) vera ⇒ P(n+1) sarà vera?   Ipotesi (I)
  3. Quindi P(n+1) = P(n) + 180°, perché? Perché se aggiungo un lato al poligono iniziale è come se aggiungessi un angolo di 180°   Tesi (T)

img_20180922_201417.jpg

  1. P(n) + 180 = [(n-2) * 180] +180   
  2. {[(n-2)*1]+1}  *180 , ho raccolto il 180 tra le quadre e graffe
  3. ma banalmente [(n-2)*1] +1 = (n-2)+1 e tutta l’espressione [(n-2)+1]  è P(n)+180 = P(n+1) la Tesi (T) 

Il metodo di induzione è un metodo diretto di dimostrazione.

#A11-#E


fullsizerender.jpg

  1. sommatoria che da k=1 va a n di un’equazione. Come primo step levo la radice al denominatore moltiplicando sia num. che den. stesso per √k per semplificarmi i calcoli. Chiaramente nel farlo anche a n non serve perché sarebbe come moltiplicare (√k/√k=1), quindi n rimane invariato. Infine per il principio di induzione supponendo vera la condizione d’esistenza per ogni n≥1 ∈ N faccio arrivare la sommatoria fino a n+1ricordando che k,n∈ N
  2. Aggiungo alla f(n) = √n l’ f(n+1)  corrispondente di √k/k cioè √k+1/k+1 , trovo il den. comune e svolgendo i calcoli sapendo che k=1 il risultato mi porta in automatico ad avere √n+1

img_5705.jpg

 

#11A Ricorsione Forte: Fibonacci e forme Induttive


Principio di Induzione

I Forma

  1. abbiamo P(n) 
  2. P(0) è vera – Peano
  3. P(k) è vera  ⇒ P(k+1) è vera

E qui la ricorsione è data dall’affermazione della proposizione P che se vale per k+1allora vale per n. La stessa la si trova nella seguente analogia

x+0=x,     x+S(y) = S(x+y)

x*0=x,   x*S(y) = x*y + x

x^0=1,    x^n+1 = x^n*x   [oppure]   x^n-1*x = x^n

Fibonacci nel un esempio singolare di induzione in quanto come serie numerica tiene conto di ben 2 numeri precedenti i quali sommati danno il terzo. La curiosità è che tutta la serie dà come immagine una funzione di restrizione dei N naturali formata dai sottoinsiemi in H al variare di i<n

IMG_5698

w = N numeri naturali

II Forma

  1. abbiamo P(n)
  2. P(0) è vera
  3. allora ¥m>0, se A(k) è Vera ¥0≤k<m, ⇒ A(m) è Vera, quindi
  4. A(n) è vera ¥n∈N

Qui la forma si complica ma si completa perché al posto di un indice ne abbiamo 2 cioè k,ν.

Supponiamo di avere m=4, allora la formula scritta in blu dovrebbe valere per qualsiasi 2 ≤ν ≤k ≤m perché giustamente per 0 ed 1 è già verificata come vera.

img_5702.jpg

come viene suddivisa la sommatoria prendendo come esempio m=4

Detto questo verifichiamo se per la condizione più “stretta” 2 =ν =k =m può valere per tutti gli m+1 oltre il 2.

img_5703.jpg

prima riga = f(n)= secondo membro. Seconda riga ipotesi di f(n+1) al membro di dx. Terza riga è la tesi dove aggiungo all’f(n) di sx il +1. Quarta riga affermo la tesi tramite calcoli algebrici

  1. alla prima riga riscrivo l’equazione nella forma originaria
  2. ci aggiungo, a destra la sommatoria sostitutiva di m+1 di sx. In rosso la freccia indica la stessa parte. La seconda riga è L’ipotesi induttiva che deve essere verificata, per capirci f(n+1)
  3. Prendo il secondo membro dell’uguaglianza del punto 1 e ci aggiungo il “+1″ che è la sommatoria del f(n+1). La trasformo in modo d’avere le sommatorie identiche (segante in blu)
  4. proprietà distributiva e raccolgo la parte comune del punto 3 e la moltiplico per il “+1” dei 2 indici ottenendo esattamente la formula iniziale ma con k,ν che vanno fino a m+1
Bibliografia
Dikran Dikranjan Maria Silvia Lucido – Aritmetica e Algebra
Barbieri Viale - Che cos'è un numero
Carl B.Boyer - storia della matematica

 

#8A Permutazioni e coefficienti Binomiali


Riassumendo il concetto una permutazione è un’applicazione iniettiva da un insieme finito X ad un’altro insieme finito Y dove ad uno ad uno che le x∈X vengono applicate alle y quest’ultime  saranno sempre meno da trovare in Y. La formula è la seguente:

n! = n (n-1) (n-2) (n-3) … (n – i +1)

nel quadrato di un binomio come (a+b)² = a²+2ab+b² il 2 è la permutazione di ab dove all’interno di un insieme finito di elementi abbiamo 2 modi di interpretare a*b che sono ab e ba. Nel caso di un binomio di terzo grado come (a+b)³ le rispettive permutazioni di a²b e ab² sono in quanto abbiamo solo 3 opzioni di combinazione fra loro: a²b = (aab + aba + baa) e ab² = (bba + bab + abb).

Quindi di può asserire che le permutazioni formano delle partizioni all’interno di un insieme finito chiamate più comunemente Coefficienti. Nel nostro caso Binomiali.
La formula
per stabilire un coefficiente binomiale è ricavata tramite il principio di induzione dell’insieme delle parti dove all’interno di ogni C stanno tutte le possibili permutazioni al variare degli elementi n dell’insieme.

Va da sé che C è una partizione di X = {C i∪¥ i,jI : X = P(X)}

Questa relazione stretta tra Insieme delle parti, partizione di un insieme e permutazioni portò Isaac Newton a formulare l’equazione dei coefficienti binomiali dove l’intera relazione trova nella sommatoria ed in condizioni di esistenza 0≤k≤n dei vari coefficienti, una elegante e non scontata coerenza.
In sintesi ragioniamo sugli esponenti che corrispondono al numero di elementi di ogni partizione, sui coefficienti come quantità di “possibili formazioni” in relazione agli elementi stessi e con la sommatoria come segmento da traslare avanti ed indietro nell’espressione, ed avremo unito per induzione ben tre concetti in uno!

IMG_5662

seconda riga si sostituisce (a+b)^n con la sommatoria analoga. terza riga si moltiplica la sommatoria per a e b in verde, poi si opera sull’ordine della sommatoria. quarta riga si raccolgono i coefficiente grazie all’uguaglianza di a^n-kb^k e poi si sommano. ultima riga aggiungo i termini estremi a^n e b^n ristabilendo il numero di elementi della sommatoria totale.

esempio:

  • (a+b)³ = insieme X
  • a³ + 3a²b + 3ab² + b³ = partizioni di X
  • 3 = Coefficiente Binomiale = numero permutazioni possibili
  • a²b = elementi del sottoinsieme relazionato al CB (in questo caso 3)
Bibliografia
Dikran Dikranjan Maria Silvia Lucido – Aritmetica e Algebra
Barbieri Viale - Che cos'è un numero
Carl B.Boyer - storia della matematica

 

 

 

 

 

Metodo induttivo


img_5219.jpg

Guardando l’enunciato ricordarsi sempre di identificare cosa sto guardando. In questo caso un’uguaglianza tra una progressione numerica (sommatoria) ed una frazione.

Poi verificarne la veridicità tramite sostituzione, tenendo conto delle condizioni di esistenza. (Perché il contesto in cui si opera è la cosa più importante che chiunque, in qualsiasi situazione, prima di prendere una decisione e portarla fondo deve avere ben chiaro) – in questo caso “per ogni intero >=1.

img_5220.jpg

Ok è vera. Si fa questo passaggio perché altrimenti staremmo dimostrando l’enunciato nel campo dell’assurdo; sarebbe come fare i 100mt sulla terra con le pinne!

Ora, appurata questa uguaglianza come ipotesi vera dico che vale anche per ogni +1 che metto ad n, quindi la mia tesi dovrebbe portarmi ad un risultato del genere

img_5221.jpg

A questo punto se l’ipotesi l’ho dimostrata ed è vera mi manca solo da dimostrarne la tesi

img_5222-e1504361752520.jpg
queste due operazioni in realtà sono la stessa, cambia solo la parte verde, ma perché per dimostrare che venga lo stesso risultato ho bisogno di scambiare la sommatoria con la frazione

Questo passaggio è spesso delicato ed ho sottolineato i termini UGUALI con lo stesso colore.
Perché dico uguali? Perché in questo caso la sommatoria è la frazione. Basta sostituirla e risolvere per vedere se riesco ad ottenere lo stesso risultato.

img_5223.jpg

primo passaggio denominatore comune, secondo passaggio raccoglimento parziale 5^n+1, quarto passaggio estraggo 5 da 20n+15 e lo moltiplico per 5^n+1 dandomi 5^n+2.

il risultato ottenuto è lo stesso dell’immagine precedente. Uguaglianza dimostrata.

Ricordate il significato delle parole: In-durre per De-durre, trarre dentro (4^ immagine sostituzione delle parti verdi) per trarre da (5^ immagine la dimostrazione).
Elegante nella forma no?

 

BIBLIOGRAFIA:
CARL B.BOYER – STORIA DELLA MATEMATICA
RICHARD COURANT E HERBERT ROBBINS – CHE COS’È LA MATEMATICA

Induzione: Bernoulli e la Nostra disuguaglianza


m

l’ipotesi non è un concetto banale per comprendere il principio; basta sostituire un numero (1,2,3,4…n o p) che soddisfi le condizioni di esistenza per dedurne nel particolare la veridicità

m2.jpg

A- primo passaggio proprietà della potenze su (1+p)^n * (1+p)

“np^2 diventa trascurabile” potrebbe stridere ma in verità si tratta di flessibilità mentale in quanto spesso capita in alcune operazioni di scremare (qui è l’esempio di una sommatoria) per non perdere la richiesta dell’enunciato.
Piccolo consiglio: in matematica mai complicarsi la vita e viaggiare sempre leggeri.

 

BIBLIOGRAFIA:
CARL B.BOYER – STORIA DELLA MATEMATICA
RICHARD COURANT E HERBERT ROBBINS – CHE COS’È LA MATEMATICA