[CBPM] TSpé - CH1 - Récurrence
32 flashcards · Mathematics · by Carine Brun
Quelles sont les caractéristiques d'une propriété que l'on peut montrer par récurrence ?
La propriété doit : être une égalité ou une inégalité porter sur les entiers naturels N\mathbb{N}N avoir un lien entre le rang kkk et le rang k+1k+1k+1 (relation de récurrence pour les suites)
On considère la suite (un)(u_n)(un) définie pour tout entier naturel n≥1n \geq 1n≥1 par u1=13u_1=\frac{1}{3}u1=31 et un+1=13(1−un)u_{n+1}=\frac{1}{3}(1-u_n)un+1=31(1−un) On veut démontrer que pour tout entier naturel n≥1n \geq 1n≥1 on a : un=14[1−(−13)n]u_n=\frac{1}{4}\left[1-\left(-\frac{1}{3}\right)^n\right]un=41[1−(−31)n] Peut-on faire une récurrence ?
OUI car : la propriété est une égalité elle porte sur les entiers naturels On a une relation de récurrence pour la suite
On veut montrer que pour tout entier n≥4n \geq 4n≥4 , 2n≥n22^n \geq n^22n≥n2 . Peut-on faire une récurrence ?
OUi car : la propriété est une inégalité elle porte sur les entiers naturels il y a un lien entre le rang kkk et le rang k+1k+1k+1 du membre de gauche. en effet 2k+1=2k×22^{k+1}=2^k \times 22k+1=2k×2
Combien il y-a-t-il d’étapes pour rédiger une récurrence ? Et quelles sont-elles ?
4 étapes : Propriété à énoncer Initialisation Hérédité Conclusion
Comment rédiger une récurrence ?
● La propriété P au rang nnn est : « …….. » ● Initialisation au rang …. ….… Ainsi P est vraie au rang …. ● Hérédité: Soit k∈Nk \in \mathbb{N}k∈N Supposons P est vraie au rang kkk (soit ...) Montrons que P est vraie au rang k+1k+1k+1 (donc montrons ......) ...... ...... ● Conclusion : P est initialisée au rang .... et héréditaire Donc ∀n∈N\forall n \in \mathbb{N}∀n∈N , ……
On considère la suite (un)(u_n)(un) définie pour tout entier naturel n≥1n \geq 1n≥1 par u1=13u_1=\frac{1}{3}u1=31 et un+1=13(1−un)u_{n+1}=\frac{1}{3}(1-u_n)un+1=31(1−un) On veut montrer par récurrence que pour tout entier naturel n≥1n \geq 1n≥1 on a : un=14[1−(−13)n]u_n=\frac{1}{4}\left[1-\left(-\frac{1}{3}\right)^n\right]un=41[1−(−31)n] Quelle est la propriété au rang nnn ?
la propriété P est rang nnn est : " un=14[1−(−13)n]u_n=\frac{1}{4}\left[1-\left(-\frac{1}{3}\right)^n\right]un=41[1−(−31)n] "
On veut montrer par récurrence que pour tout entier n≥4,2n≥n2n\geq 4, 2^n \geq n^2n≥4,2n≥n2 Quelle est la propriété au rang nnn ?
La propriété P au rang nnn est : " 2n≥n22^n \geq n^22n≥n2 "
On veut démontrer par récurrence qu'une suite (un)(u_n)(un) est croissante et majorée par 2. Quelle est la propriété P au rang nnn ?
la propriété P au rang nnn est : " un≤un+1≤2u_n\leq u_{n+1} \leq 2un≤un+1≤2 "
Comment rédiger l'initialisation d'une récurrence ?
Méthode : Calculer SEPAREMENT les 2 membres Constater l'égalité ou l'inégalité Conclure que la propriété est vraie au rang initial Rédaction : ● Initialisation au rang ... membre gauche = ..... et membre droite = .... on a membre gauche .... membre droite Donc P est vraie au rang ...
On considère la suite (un)(u_n)(un) définie pour tout entier naturel n≥1n \geq 1n≥1 par u1=13u_1=\frac{1}{3}u1=31 et un+1=13(1−un)u_{n+1}=\frac{1}{3}(1-u_n)un+1=31(1−un) On veut démontrer que pour tout entier naturel n≥1n \geq 1n≥1 on a : un=14[1−(−13)n]u_n=\frac{1}{4}\left[1-\left(-\frac{1}{3}\right)^n\right]un=41[1−(−31)n] A quel rang doit-on faire l'initialisation ?
initialisation au rang 1
On considère la suite (un)(u_n)(un) définie pour tout entier naturel par u0=1u_0=1u0=1 et un+1=13(1−un)u_{n+1}=\frac{1}{3}(1-u_n)un+1=31(1−un) On veut démontrer que pour tout entier naturel un≥0u_n \geq 0un≥0 A quel rang doit-on faire l'initialisation ?
initialisation au rang 0
On veut montrer par récurrence que pour tout entier n≥4n \geq 4n≥4 , 2n≥n22^n \geq n^22n≥n2 . A quel rang doit-on faire l'initialisation ?
initialisation au rang 4
Qu'est-ce que l'hypothèse de récurrence?
C'est la propriété P supposée vraie au rang nnn dans l'hérédité
Qu'est-ce que la relation de récurrence?
C'est la relation qui relie les termes consécutifs d'une suite Dans la plupart des cas, c'est la relation qui donne un+1u_{n+1}un+1 en fonction de unu_nun Par exemple : un+1=2un+5u_{n+1}=2u_n+5un+1=2un+5
Comment justifier l'hérédité si la propriété est une égalité AVEC suites ?
Partir de la relation de récurrence Puis utiliser l'hypothèse de récurrence
Comment justifier l'hérédité si la propriété est une inégalité AVEC suites ?
Partir de l'hypothèse de récurrence uk≤5u_k \leq 5uk≤5 puis faire des opérations sur les inégalités ( à trouver grâce à la relation de récurrence)
On considère la suite (un)(u_n)(un) définie pour tout entier naturel n≥1n \geq 1n≥1 par u1=13u_1=\frac{1}{3}u1=31 et un+1=13(1−un)u_{n+1}=\frac{1}{3}(1-u_n)un+1=31(1−un) On veut démontrer que pour tout entier naturel n≥1n \geq 1n≥1 on a : un=14[1−(−13)n]u_n=\frac{1}{4}\left[1-\left(-\frac{1}{3}\right)^n\right]un=41[1−(−31)n] Comment rédiger l'hérédité ?
Hérédité : Soit k∈N∗k \in \mathbb{N}^*k∈N∗ Supposons P est vraie au rang kkk càd uk=14[1−(−13)k]u_k=\frac{1}{4}\left[1-\left(-\frac{1}{3}\right)^k\right]uk=41[1−(−31)k] Montrons que P est vraie au rang k+1k+1k+1 càd montrons que uk+1=14[1−(−13)k+1]u_{k+1}=\frac{1}{4}\left[1-\left(-\frac{1}{3}\right)^{k+1}\right]uk+1=41[1−(−31)k+1] D'après la relation de récurrence uk+1=13(1−uk) u_{k+1}=\frac{1}{3}(1-u_k) uk+1=31(1−uk) On utilise alors l'hypothèse de récurrence uk+1=13(1−14[1−(−13)k]) u…
Comment justifier l'hérédité si la propriété est une égalité SANS suite ?
Ecrire le lien entre le rang kkk et le rang k+1k+1k+1 pour l'un des 2 membres (celui pour lequel on le voit facilement) Puis utiliser l’hypothèse de récurrence
Comment justifier l'hérédité si la propriété est une inégalité SANS suite ?
Partir de l'hypothèse de récurrence puis faire des opérations sur les inégalités (à trouver seul)
Considérons la suite (un)(u_n)(un) définie par u0=1u_0=1u0=1 et pour tout n∈Nn\in \mathbb Nn∈N , un+1=2+unu_{n+1}=\sqrt{2+u_n}un+1=2+un Démontrer par récurrence que pour tout entier n∈N,0≤un≤2n \in \mathbb N , 0 \leq u_n \leq 2n∈N,0≤un≤2
La propriété P au rang nnn est : " 0≤un≤20≤u_n≤20≤un≤2 " Initialisation au rang 0 u0=0u_0=0 u0=0 on a bien 0≤u0≤2 0≤u_0≤20≤u0≤2 Donc P est vraie au rang 0 Hérédité : Soit k∈Nk \in \mathbb Nk∈N Supposons P est vraie au rang kkk càd 0≤uk≤20 ≤ u_k ≤ 20≤uk≤2 Montrons que P est vraie au rang k+1k+1k+1 càd montrons que 0≤uk+1≤20 ≤ u_{k+1} ≤ 20≤uk+1≤2 D'après l’hypothèse de récurrence 0≤uk≤20 ≤ u_k ≤ 20≤uk≤2 2≤uk+2≤4 2 ≤ u_k +2≤ 4 2≤uk+2≤4 2≤uk+2≤4 \sqrt 2 ≤ \sqrt{u_k +2} ≤ \sqrt 4 2 ≤uk+2 ≤…
Comment trouver les opérations à faire dans l'hérédité pour montrer une inégalité?
grâce à la relation de récurrence pour les suites OU seul en cherchant un lien entre l'un des 2 membres de l'expression au rang k et au rang k+1
Quelles sont les opérations à faire dans l'hérédité pour démontrer une propriété sur une suite définie par la relation un+1=3un+4u_{n+1}=3u_n+4un+1=3un+4 ?
multiplier par 3 ajouter 4
Quelles sont les opérations à faire dans l'hérédité pour démontrer une propriété sur une suite définie par la relation un+1= 3un+4u_{n+1}= \sqrt{\frac{3}{u_n}+4} un+1= un3+4 ?
fonction inverse multiplier par 3 ajouter 4 fonction racine carrée
On veut montrer par récurrence que pour tout entier n≥4,2n≥n2n \geq 4, 2^n \geq n^2n≥4,2n≥n2 Quelles sont les étapes pour justifier l'hérédité ?
juste multiplier par 2 En effet : 2k≥k22^k \geq k^22k≥k2 2k×2≥k2×22^k \times 2 \geq k^2 \times 22k×2≥k2×2 2k+1≥2k22^{k+1} \geq 2k^22k+1≥2k2 Reste à prouver que 2k2≥(k+1)22k^2 \geq (k+1)^22k2≥(k+1)2 ce qui n'est pas facile mais cela ne correspond pas à une difficulté liée à la récurrence... Pour comparer 2 expressions, étudions le signe de leur différence : 2k2−(k+1)2=k2−2k−12k^2-(k+1)^2=k^2-2k-12k2−(k+1)2=k2−2k−1 Le trinôme du second degré k2−2k−1k^2-2k-1k2−2k−1 a pour discriminant Δ=8\Delta =…
On a un+1=f(un)u_{n+1}=f(u_n)un+1=f(un) . On veut montrer une propriété par récurrence sur la suite (un)(u_n)(un) . Quelles sont les étapes à faire pour justifier l'hérédité?
une seule étape : utiliser la fonction fff Attention : Si la propriété à démontrer est une inégalité, il faudra justifier que l'ordre est conservé car la fonction fff est croissante sur I.
On considère la suite (un)(u_n)(un) définie pour tout entier naturel n≥1n \geq 1n≥1 par u1=13u_1=\frac{1}{3}u1=31 et un+1=13(1−un)u_{n+1}=\frac{1}{3}(1-u_n)un+1=31(1−un) On veut démontrer par récurrence que pour tout entier naturel n≥1n \geq 1n≥1 on a : un=14[1−(−13)n]u_n=\frac{1}{4}\left[1-\left(-\frac{1}{3}\right)^n\right]un=41[1−(−31)n] Comment rédiger l'initialisation ?
Initialisation au rang 1 u1=13u_1=\frac{1}{3} u1=31 et 14[1−(−13)1]=14[1+13]=14×43=13\frac{1}{4}\left[1-\left(-\frac{1}{3}\right)^1\right]=\frac{1}{4}\left[1+\frac{1}{3}\right]=\frac{1}{4}\times\frac{4}{3}=\frac{1}{3}41[1−(−31)1]=41[1+31]=41×34=31 On a bien u1=14[1−(−13)1]u_1=\frac{1}{4}\left[1-\left(-\frac{1}{3}\right)^1\right]u1=41[1−(−31)1] Donc P est vraie au rang 1
Une propriété P vraie au rang n = 6 et héréditaire à partir du rang n = 5 est-elle vraie pour tout n ≥ 10 ?
Oui
Une propriété P vraie au rang n = 5 et héréditaire à partir du rang n = 6 est-elle vraie pour tout n ≥ 10 ?
Non
Une propriété P vraie au rang n = 6 et héréditaire à partir du rang n = 5 est-elle vraie pour tout n ≥ 5 ?
Non
Une propriété P vraie au rang n = 6 et héréditaire à partir du rang n = 5 est-elle vraie pour tout n ≥ 6 ?
Oui
Est ce que toutes les propriétés peuvent se démontrer par récurrence ?
Non il faut que la propriété soit sur N\mathbb NN
Est ce que toutes les propriétés sur N\mathbb{N}N peuvent se démontrer par récurrence ?
Non il faut aussi connaitre un lien entre le rang n et le rang n+1 (relation de récurrence ou lien à trouver !)