Ingegneria Energetica - Analisi e Geometria 1

Numeri interi

Divided by topic

I numeri interi Teorema 1. (divisione inZ) Sianoa; b2Z,b6 = 0. Al lora esistono e sono uniciq; r2Z tali che (1)a=bq+r (2) 0r < > :a 0= 0 a1= 1 an= a n1+ a n2: Questa successione venne introdotta dal mercante italiano Fibonacci (Leonardo Pisano, 1180 circa - 1250) nel suo "Liber Abaci" come soluzione del problema delle coppie di conigli. Esercizio 1.Utilizzando la 2a forma del principio di induzione completa si dimostra la seguente proprieta dei numeri di Fibonacci: 8k2N ; n2N an+k= a ka n+1+ a k1a n: Esercizio 2.Utilizzando la 1a forma del principio di induzione completa si prova che due numeri di Fibonacci successivi sono coprimi, ossia hanno massimo comun divisore 1. Per le successioni denite per ricorrenza e sempre possibile individuare una formula chiusa, ovvero una formula che descriva direttamente l'n-mo termine della successione. E ben noto che an =a
: : :
a |{z} nvolte: Inoltre, il fattoriale e stato denito come:n! =n
(n1)
(n2)
: : :
2
1: 5 Si verica facilmente che le due formule precedenti corrispondono alle formule chiuse delle cor- rispondenti successioni denite per ricorrenza e inoltre che la formula chiusa per la progressione aritmetica e:an= a+nd e per la progressione geometrica:an= a
dn : Per quanto riguarda le torri di Hanoi, si puo ricavare la formula chiusa osservando che: an= 2 a n1+ 1 = 2(2 a n2+ 1) + 1 = 4a n2+ 2 + 1 = 4(2 a n3+ 1) + 2 + 1 = 8a n3+ 4 + 2 + 1 = 8(2 a n4+ 1) + 4 + 2 + 1 = 16a n4+ 23 + 22 + 21 + 20 =n X i=12 i 1 : Esercizio 3.Provare per induzione completa che n X i=12 i 1 = 2n 1: In conclusione la formula chiusa per la succesione relativa al gioco delle torri di Hanoi e:an= 2n 1: La formula chiusa per i numeri di Fibonacci e (senza verica): an=1p 5 1 +p5 2 ! n 1p5 2 ! n! : Il numero  =1+p5 2 viene chiamato "rapporto aureo" o "proporzione divina".