Fibonacci

[hark]

Siano F di zero,F di uno, F di due...... i numeri di Fibonacci. Dimostrare che per ogni n> o uguale a 0 (F di n, F di n+1) = 1

Sapete come possa dimostrarla per induzione? In altri modi ci sono riuscito, ma per induzione no...

Grazie mille in anticipo

[hark]

uppete

[leev]

cosa significa quel 0 (F di n, F di n+1) ?

[anonymous_be1147]

cosa significa quel 0 (F di n, F di n+1) ?

Massimo Comun Divisore. Se non ricordo male è un esercizio tratto dal libro "Introduction to Analytic Number Theory" di T. Apostol.

[hark]

grazie mille

[Salamandra]

Scusate, temo di non aver capito bene: $0$ sarebbe il MCD di due numeri? E l'uno che fine ha fatto?

[TomSawyer]

"0 (F di n, F di n+1) = 1". 0 e' il simbolo usato per la funzione.

[anonymous_be1147]

Scusate, temo di non aver capito bene: $0$ sarebbe il MCD di due numeri? E l'uno che fine ha fatto?

No, ho sbagliato il quoting, lo zero non c'entra.

L'esercizio è

The Fibonacci sequence ` 1, 1, 2, 3, 5, 8, 13, 21, 34, ... ` is defined by the recursion formula ` a_{n+1} = a_n + a_{n-1} `, with ` a_1 = a_2 = 1 `. Prove that ` (a_n, a_{n+1}) = 1 ` for each ` n `.

e la notazione ` (a_n, a_{n+1}) ` indica appunto il MCD. Hark fa partire la sequenza con `a_0` e quindi la relazione va dimostrata ` \forall n \ge 0 `

[fu^2]

allora prima di dim quello, devo dimimostrare che ogni due "posti" dispari c'è un "posto" pari...

1,1,2,3,5,8,...

$a_1=1
$a_2=1
$a_3=2
...

1.verifico per $a_1,a_2$(1+1) =2

2.pongo vero per ogni n, quindi per $a_n$

3.verifico per $a_(n+1)$
$a_(n+1)+a_(n)=a_(n+2)$

sappiamo che numero pari si può scrivere cm 2k
mentre un numero dispari come 2k+1

quindi sle combinazioni di valori che possono assumere a(n) e a(n+1) sono tre
$a_n=2k
$a_(n+1)=2k

però questo non possiamo accettarlo, in quanto se fossero due pari, tutta la serie dovrebbe essere composta da numeri pari, ma il proimo termine è dispari e quindi non possiamo accettarla.

o

$a_n=2k+1
$a_(n+1)=2k+1
$a_(n+2)=a_n+a_(n+1)=2k+1+2k+1=4k+2$ che è un numero pari

o

$a_n=2k
$a_(n+1)=2k+1
$a_(n+2)=a_n+a_(n+1)=2k+2k+1=4k+1$ che è un numero dispari

quindi questa prima parte è dimostrata.

PASSIAMO AL QUESITO
1.verifico per $a_1,a_2$(1+1) MCD=1
2.pongo vero per n
3.verifico per $a_(n+1)$
quindi $(a_(n+1),a_(n+2))=(a_(n-1)+a_n,a_n+a_(n+1))$

quindi come dimostrato prima possiamo scrivere, posto che a_n è dispari

$(2k+1+2k+1,2k+1+2k)=(4k+2,4k+1)$ l'MCD tra 4k+2 e 4k+1 è soltanto 1, l'ipotesi è dimostarta. giusto?