Exercise:
textbfFibonacci La sequenza di Fibonacci è una famosa sequenza numerica definita come segue: F_ F_ F_n+F_n+F_n-quad ngeq abclist abc Calcola i primi termini della serie di Fibonacci. abc Dimostra textbfper induzione che la sequenza soddisfa l'identità F_n-F_n+ - F_n^ -^n. tagIdentità di Cassini abc Considera ora serie ricorsiva definita come a_qquad a_n++fraca_n. Dopo averne calcolato i primi termini mettili in frazione ipotizza un legame con la successione di Fibonacci e verifica l'ipotesi per textbfinduzione. abc Difficile Dimostra textbfper induzione che la sequenza è data dalla formula esplicita F_nfracvarphi^n--varphi^-nvarphi- dove varphifrac+sqrt è il rapporto aureo il quale soddisfa varphi+varphi^-. abclist

Solution:
abclist abc I primi termini della successione sono hrefhttps://oeis.org/Adots abc Procediamo con ordine itemize item F_n-F_n+ - F_n^ -^n. Identità di Cassini Il caso base n è banalmente vero in quanto - --^quad checkmark Asiamo dunque che lo statement sia valido per n allora abbiamo che per n+ * F_nF_n+ - F_n+^ F_nF_n + F_n+-F_n+F_n- + F_n & F_n^ + F_nF_n+ -F_n-F_n+ - F_nF_n+ F_n^ - F_n-F_n+ --^n-^n+quad checkmark * da cui si conclude che vale per tutte le ngeq item F_n- F_n^ + F_n-^quad forall ngeq Il caso base n è banalmente vero ^+^. Se asiamo che valga per n allora per n+ * F_n+F_n+F_n-F_n * item F_n F_n-+F_nF_nquad forall ngeq . Notiamo che * F_n F_n- + F_n- F_n- + F_n- F_n- + F_n- F_n- + F_n- vdots F_i+ F_n-i + F_i F_n-i- * In particolare per in- abbiamo che F_n F_nF_n+ + F_nF_n-. E dunque verifichiamo che * F_nF_n+ + F_nF_n- F_n+-F_n-F_n+ + F_nF_n- F_n+^ - F_n+F_n- + F_nF_n- F_n+^ - F_n + F_n-F_n- + F_nF_n- F_n+^ - F_n-^. * itemize abc Calcoliamo i primi termini: * a_n_nleftfracfracfracfracdots.right * Guardando con attenzione numeratore e denominatore riconosciamo relativamente chiaramente due sequenze di Fibonacci una a numeratore ed una denominatore. La nostra ipotesi è dunque a_nfracF_n+F_nquad ngeq . Verifichiamola formalmente: a_fracF_F_fracquad checkmark e inoltre a_n++fraca_n+fracF_nF_n+fracF_n+F_n+F_n+fracF_n+F_n+quad checkmark. abc Verifichiamo le due proprietà di partenza: * F_fracvarphi^--varphi^-varphi-frac-varphi- checkmark F_fracvarphi^--varphi^-varphi-fracvarphi+varphi^-varphi-fracvarphi+varphi-varphi-fracvarphi-varphi- checkmark * Dove abbiamo utilizzato l'identità varphi+varphi^-iff varphi^-varphi-. Da ultimo il passo di induzione: * F_n+F_n+F_n-fracvarphi-leftvarphi^n+-varphi^-n+varphi^n-+-varphi^-n-right fracvarphi-left+varphi^-varphi^n+-varphi-varphi^-nright fracvarphi-leftvarphi varphi^n+-varphi^--varphi^-nright fracvarphi-leftvarphi^n++-varphi^-n+right * dove nel terzo abbiamo utilizzato l'identità varphi+varphi^-iff -varphi-varphi^-. abclist