Suites récurrentes & arithmétique

[Patrick]

Bonsoir,

Voici un problème sur le thème des suites associé à l’arithmétique.
Je pense avoir rédigé l'essentiel, même si je ne suis très sûr des démonstrations en 2c et 2d.
J'ai facilité la lecture un peu longue avec LaTex, Merci pour la vérification.

1) Déterminer le PGCD de \(4^2 - 1\) et de \(4^6 - 1\)

2) Soit \((u_n)\) la suite définie par :
\(\quad\forall n\in\mathbb{N}\quad u_{n+2}=5u_{n+1}-4u_n\) avec \(u_0=0\), \(u_1=1\)
- a. Calculer \(u_2\), \(u_3\) et \(u_4\),
- b. Démontrer que, \(\forall n\in\mathbb{N}\) : \(u_{n+1}=4u_n+1\),
- c. Démontrer que, \(\forall n\in\mathbb{N}\), \(u_n\) est un entier naturel,
- d. En déduire, \(\forall n\in\mathbb{N}\), le PGCD de\(u_n\) et de \(u_{n+1}\).

3) Soit \((v_n)\) la suite définie par : \(\forall n\in\mathbb{N},\quad v_n = u_n+\frac{1}{3}\)
- a. Démontrer que \((v_n)\) est une suite géométrique,
- b. \(\forall n\in\mathbb{N}\), exprimer \(v_n\), puis \(u_n\), en fonction de \(n\),
- c. Déterminer, \(\forall n\in\mathbb{N}\), le PGCD de \(4^n- 1\) et de \(4^{n+1}-1\).
_____________________________________________________

1) Rappels utiles : \(a^3-b^3=(a-b)(a^2+ab+b^2)\) et \(a|b\quad\Longleftrightarrow\quad pgcd(a,b)=a\).
Compte tenu des rappels, on peux répondre à la question : \(4^6-1=(4^2)^3-1=(4^2-1)[(4^2)^2+1\times 4^2+1]\quad\Longleftrightarrow\quad pgcd(4^2 - 1,\ 4^6 - 1)=4^2 - 1\).

2) a. Les premiers termes de \((u_n)\) sont :
\(u_0=0,\ u_1=1,\ u_2=5,\ u_3=21,\ u_4=85\).
\(\quad\)b. Démonstration par récurrence :
Initialisation Ok, car \(u_1=4\times u_0+1=4\times 0+1=1\),
Récurrence : on suppose \(u_{n+1}=4u_n+1\quad\Longleftrightarrow\quad u_{n+1}-1=4u_{n}\) vrai.
Donc par substitution : \(u_{n+2}=5u_{n+1}-(u_{n+1}-1)=4u_{n+1}+1\)
Conclusion : la preuve est faite, car \(u_{n+2}=4u_{n+1}+1\) est le rang \(n+1\) de \(u_{n+1}=4u_n+1\).
\(\quad\)c. On sait que \(u_0=0\) est un entier naturel et je suppose que \(u_n=4u_{n-1}+1\) aussi, alors \(4\times u_n\) est un entier, de même que \(u_{n+1}=4u_{n}+1\) CQFD ?
\(\quad\)d. Maintenant que l'on sait qu'il existe des entiers \(u_{n+1}\) et \(u_n\), grâce au théorème de BEZOUT, on peut affirmer que le \(pgcd(u_{n+1},u_n)=1\), puisque \(u_{n+1}-4u_{n}=1\) et les coefficients \(1\) et \(-4\) sont premiers entre eux. CQFD ?

3) a Concernant la relation entre les suites \((u_n)\text{ et }(v_n)\) nous avons :
\(\left\(v_n=u_n+\frac{1}{3}\quad\text{et}\quad v_{n+1}=u_{n+1}+\frac{1}{3}\right)\quad\Longleftrightarrow\quad\left\(u_n=v_n-\frac{1}{3}\quad\text{et}\quad u_{n+1}=v_{n+1}-\frac{1}{3}\right)\)
Comme \(u_{n+1}=4u_n+1\) il s'en suit que :
\(v_{n+1}-\frac{1}{3}=4\times(v_n-\frac{1}{3})+1\quad\Longleftrightarrow\quad v_{n+1}=4v_n-\frac{4}{3}+1+\frac{1}{3}=4v_n\).
C'est bien une suite géométrique et sa raison \(q=4\).
\(\quad\)b. On en déduit que : \(v_{n+1}=4\times v_n\) et \(v_0=u_0+\frac{1}{3}=\frac{1}{3}\).
Maintenant, il est possible d'exprimer \(v_n\) en fonction de \(n\) : \(v_n=v_0\times 4^n=\frac{1}{3}\times 4^n\).
Compte tenu de la relation : \(u_n=v_n-\frac{1}{3}\), on exprime ainsi \(u_n\) en fonction de \(n\) :
\(u_n=\frac{1}{3}\times 4^n-\frac{1}{3}=\frac{1}{3}\times\left(4^n-1\right)\).
\(\quad\)c. Un petit rappel : \(pgcd(ka,kb)=k\times pgcd(a,b)\),
\(u_n=\frac{1}{3}\times\left(4^n-1\right)\Leftrightarrow 3u_n=4^n-1\)
\(u_{n+1}=\frac{1}{3}\times\left(4^{n+1}-1\right)\Leftrightarrow 3u_{n+1}=4^{n+1}-1\)
Donc on a : \(pgcd(4^n-1,\ 4^{n+1}-1)=pgcd(3u_n,\3u_{n+1})\)
\(pgcd(4^n-1,\ 4^{n+1}-1)=3\times pgcd(u_n,u_{n+1})=3\times 1=3\).

J'espère avoir utilisé les équivalences à bon escient ?
Encore Merci.

@+

[sos-math(12)]

Bonjour : Il me semble qu'il n'y a rien à redire de l'ensemble.

Pour le 2.c tu pourrais peut être faire apparaître les parties initialisation et propagation de ta démonstration par récurrence et signaler que tu vas faire une démonstration par récurrence.
Pour le 2.d tu devrais peut être dire "maintenant que l'on sait que \(u_{n+1}\) et \(u_n\) sont toujours des entiers naturels.
Petite remarque : la version de Tex utilisée par le logiciel n'aime pas les expressions commençant par - (ce qu'elle traduit par \(-4\)) comme en témoigne ton sujet.

Bonne continuation.

[Patrick]

Merci beaucoup pour la vérification et les conseils.
\(-4\) et avec un espace\(\ -4\)