Une récurrence avec Python

On définit une suite {(a_n)_{n\ge0}} par {a_0=1} et : {\forall\,n\in\mathbb{N},\;\begin{cases}a_{2n+1}=a_n\cr a_{2n+2}=a_{n}+a_{n+1}\end{cases}}

Question 1.
Soient {r} et {s} deux entiers premiers entre eux.
Montrer qu’il existe {n} tel que {\begin{cases}a_n=r\\a_{n+1}=s\end{cases}}
Indication : récurrence forte sur la valeur de {r+s}.
Cliquer ici pour voir (ou cacher) la réponse
Si {r+s=2}, donc si {r=s=1}, c’est évident car {a_0=1} et {a_1=1}.

On se donne {r,s} premiers entre eux, avec {r+s>2} (ils sont donc distincts).

On suppose la propriété vraie pour les entiers {r',s'} premiers entre eux tels que {r'+s'\lt r+s}.

  • Si {r>s}, alors par hypothèse de récurrence, il existe {m} tel que {a_m=r-s} et {a_{m+1}=s} (car {r-s} et {s} sont premiers entre eux).
    On a alors {a_{2m+2}=r} et {a_{2m+3}=s}.
  • Si {r\lt s}, alors par hypothèse de récurrence, il existe {m} tel que {a_m=r} et {a_{m+1}=s-r}.
    On a alors {a_{2m+1}=r} et {a_{2m+2}=s}.

Dans tous les cas, on a trouvé {n} dans {\mathbb{N}} tel que {a_n=r} et {a_{n+1}=s}, ce qui achève la récurrence.

Question 2.
Écrire une fonction Python «a», prenant en argument un entier {n\ge0}, et renvoyant {a_{n}}.
La fonction «a» utilisera bien sûr la définition récursive de la suite {(a_{n})_{n\ge0}}.
Pour mémoriser les appels récursifs, on utilisera un dictionnaire {A} formé d’enregistrements {k :a_{k}}, initialisé par {A=\{0 :1\}} c’est-à-dire {a_{0}=1}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
Question 3.
Écrire quelques lignes de Python pour afficher les 100 premières valeurs de la suite {a} dans un tableau {10\times 10} (on recommande l’extension Numpy).
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
Question 4.
Écrire une fonction Python nommée «gcd», et calculant le pgcd de deux entiers.
Écrire une fonction Python nommée «find», prenant en arguments deux entiers naturels {r} et {s}, et renvoyant un entier {n} tel que {a_{n}=r} et {a_{n+1}=s}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).