PGCD Fibonacci

Dans cet exercice, nous étudions la suite de Fibonacci. Nous rappelons que la suite de Fibonacci est définie par U0=0, U1=1 et Un+2 = Un+1 + Un. La première question consiste à montrer que pour tout n positif, (Un+1 * Un-1 - Un^2) = (-1)^n. Pour cela, nous considérons une suite Vn définie par Vn = (Un+1 * Un-1 - Un^2). Nous souhaitons montrer que Vn est une suite géométrique de raison -1. Nous commençons par exprimer Vn+1 en fonction de Vn. En utilisant la relation de récurrence de la suite de Fibonacci, nous obtenons Vn+1 = (Un+2 * Un - Un+1^2). Nous procédons ensuite à un développement et simplifions l'expression pour obtenir Vn+1 = -Vn. Cela prouve que Vn est une suite géométrique de raison -1. En calculant V1, nous trouvons que Vn = (-1)^n. Ainsi, nous avons montré que pour tout n positif, (Un+1 * Un-1 - Un^2) = (-1)^n. La deuxième partie consiste à montrer que deux termes consécutifs de la suite de Fibonacci sont premiers entre eux. Nous utilisons l'égalité précédente pour cela. Nous remarquons que cette égalité ressemble à une égalité de Bézout. En multipliant les deux côtés de l'égalité par (-1)^n, nous obtenons U(n+1) * U(n-1) - U(n)^2 = 1. En écrivant cette égalité sous la forme U(n-1) * U(n+1) + U(n) * Un = 1, nous avons trouvé les coefficients de Bézout montrant que U(n-1) et U(n+1) sont premiers entre eux. Ensuite, nous montrons que pour tout n, U(m+n) = Um * Un+1 + Um-1 * Un. Nous utilisons une double récurrence pour démontrer cette propriété. En vérifiant les deux premiers termes de la récurrence, nous constatons que la propriété est vérifiée. Ensuite, nous supposons que la propriété est vraie pour PM et PM+1, et nous montrons qu'elle est également vraie pour PM+2. Finalement, en utilisant cette propriété, nous montrons que le PGCD de Um et Un est égal à U(PGCD(m,n)). En conclusion, nous avons étudié la suite de Fibonacci et montré plusieurs propriétés intéressantes, telles que la relation géométrique entre les termes de la suite, la coprimalité des termes consécutifs et la relation entre le PGCD de deux termes et le PGCD de leurs indices.