Chap2 - Recurrence, Sums, Products PDF

H G ar ia M xe m Chapitre 2 – Récurrence, sommes et produits pl ai re de ———————————————————————– BA SH IE ———————————————————————– BA SH IE xe Table des matières m pl ai re de M ar ia G H AF EL EH ECG1 - Antoine Lagarde 2 EH 1 Principe de récurrence Récurrence simple ....

H G ar ia M xe m Chapitre 2 – Récurrence, sommes et produits pl ai re de ———————————————————————– BA SH IE ———————————————————————– BA SH IE xe Table des matières m pl ai re de M ar ia G H AF EL EH ECG1 - Antoine Lagarde 2 EH 1 Principe de récurrence Récurrence simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Récurrence double . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 G H AF EL 1.1 4 ar ia 2 Sommes Notation et propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Changements d’indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Sommes classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.4 Sommes doubles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.4.1 Sommes doubles sur un rectangle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.4.2 Sommes doubles sur un triangle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . EH BA SH IE xe m pl ai re de M 2.1 5 7 8 EL 3 Produits 4 Factorielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Notation et propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.3 Lien entre somme et produit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 M ar ia G H AF 3.1 11 ai re de 4 En Python 8 11 xe m pl 5 Méthodes 12 FE LE H BA SH IE 6 Blind-test « Dieu a fait les nombres entiers, tout le reste est l’oeuvre de l’Homme. » 1 Leopold Kronecker Principe de récurrence 1.1 Récurrence simple H 1 ar ia G Axiome (Principe de la récurrence simple) de M Soit P(n) une propriété dépendant d’un entier n. Si pl ai re • Initialisation : P(n0 ) est vraie pour un certain entier n0 ; xe m • Hérédité : P(n) ⇒ P(n + 1) est vraie pour tout entier n ⩾ n0 ; AF EL EH BA SH IE alors P(n) est vraie pour tout entier n ⩾ n0 . Remarque. Cet axiome est aisé à admettre car il généralise le raisonnement par induction : si P (n0 ) G H est vraie, comme P (n0 ) ⇒ P (n0 + 1) alors P (n0 + 1) est vraie. Comme P (n0 + 1) ⇒ P (n0 + 2) alors ar ia P (n0 + 2) est vraie, et ainsi de suite. de M Attention. Dans l’hérédité, «l’hypothèse de récurrence» (abrégée H.R) consiste à supposer que P(n) est re vraie pour un certain n ⩾ n0 . Il ne faut pas supposer que P(n) est vraie pour tout n ⩾ n0 , car alors il n’y m pl ai a plus rien à montrer ! xe • Montrons formellement par récurrence que ∀n ∈ N, ∀x ∈ R, enx = (ex )n . SH IE Exercice 1. BA Soit P(n) la proposition « ∀x ∈ R, enx = (ex )n » pour n ∈ N. EL EH Initialisation : Soit x ∈ R, e0×x = 1 et (ex )0 = 1, donc ∀x ∈ R, e0x = (ex )0 , donc P(0) est H AF vraie. ar ia G Hérédité: Soit n ∈ N. On suppose P(n) vraie. Soit x ∈ R d’après l’hypothèse de récurrence ai re = (ex )n ex de M e(n+1)x = enx+x = enx ex x n+1 xe m pl = (e ) SH IE Donc P(n + 1) est vraie. EH BA Ainsi, d’après le principe de récurrence, ∀n ∈ N, ∀x ∈ R, enx = (ex )n AF EL • Montrons que ∀n ⩾ 2, 2n > n. ia G H Procédons par récurrence : M ar – Pour n = 2, 22 = 4 > 2 re de – Soit n ∈ N, n ⩾ 2. On suppose 2n > n. Alors d’après l’H.R, 2n+1 = 2 × 2n > 2n. ⩾2 Ainsi pour tout n ∈ N, 2n > n. BA SH IE xe m pl ai Or 2n = |{z} n +n ⩾ n + 2 > n + 1, donc 2n+1 > n + 1 FE LE H Rédaction. On distinguera dans ce cours trois types de rédaction : la rédaction «lourde», où on écrit Initialisation : , Hérédité : et où on pose P(n), la rédaction «légère», où l’on n’écrit pas ces éléments (voir ci-dessus pour les deux types de rédaction), et la rédaction «mixte», où on pose P(n) mais on n’écrit pas Initialisation : ni Hérédité :. 2 1.2 Récurrence double Axiome (Principe de la récurrence double) ar ia G H Soit P(n) une propriété dépendant d’un entier n. Si pl ai re de M • Initialisation : P (n0 ) et P (n0 + 1) sont vraies pour un certain entier n0 ;
• Hérédité : P(n) et P(n + 1) ⇒ P(n + 2) est vraie pour tout entier n ⩾ n0 ; AF EL EH Montrons que ∀n ∈ N, un = 3n . G H Procédons par récurrence double. Soit n ∈ N. On pose P(n) : « un = 3n ». ar ia – On a u0 = 30 donc P(0) est vraie, et u1 = 31 donc P(1) est vraie. de M – Soit n ∈ N un entier naturel fixé. On suppose que P(n) et P(n + 1) sont vraies. Alors : ai re un+2 = 2un+1 + 3un = 2 × 3n+1 + 3 × 3n = 3n (6 + 3) = 3n+2 xe m pl Donc P(n + 2) est vraie. SH IE On conclut que pour tout n ∈ N, un = 3n . SH IE xe m pl ai re de M ar ia G H AF EL EH BA SH IE xe m pl ai re de M ar ia G H AF EL EH BA • Soit (un ) la suite vérifiant  n u0 = u1 = 1, et pour tout n ∈ N, un+2 = un+1 + un . Montrons que pour 5 tout n ∈ N, un ⩽ . 3  n 5 ». Procédons par récurrence double. Soit n ∈ N. On pose P(n) : « un ⩽ 3  0  1 5 5 – u0 = 1 ⩽ , u1 = 1 ⩽ , donc P(0) et P(1) vraies. 3 3  n  n+1 5 5 – Soit n ∈ N. On suppose P(n) et P(n + 1) vraies. un ⩽ , un+1 ⩽ donc 3 3  n+1  n 5 5 un+2 = un+1 + un ⩽ + 3 3  n   5 5 ⩽ +1 × 3 3  n 8 5 × ⩽ 3 3  n  2  2 5 5 8 25 5 ⩽ > × car = 3 3 3 9 3  n+2 5 ⩽ 3 Donc P(n + 2) vraie.  n 5 . Ainsi pour tout n ∈ N, un ⩽ 3 FE LE H BA Remarque. On peut également définir des récurrences triples, quadruples... Tout ceci est au programme.
La récurrence forte, à savoir P(n0 ) vraie et ∀k ∈ Jn0 , nK, P(k) ⇒ P(n + 1) vraie pour tout entier n ⩾ n0 , n’est en revanche pas au programme. 3 BA • Soit (un ) la suite vérifiant u0 = 1, u1 = 3, et pour tout n ∈ N, un+2 = 2un+1 + 3un . Exercice 2. SH IE xe m alors P(n) est vraie pour tout entier n ⩾ n0 . Sommes 2.1 Notation et propriétés H 2 p⩽k⩽n M xe m n X IE Par convention, si p > n, uk . On dit que k est l’indice de la somme, et p et n k∈Jp,nK uk = 0 SH en sont les bornes. X pl ai re uk ou uk = up + up+1 + · · · + un . k=p k=p k=p Plus généralement, si A est une partie finie de N et (un ) une suite, on note X BA X n X ui la somme des AF EL EH On la note également uk par de n X Soient p, n ∈ N, avec p ⩽ n, et u une suite. On définit ar ia G Définition i∈A • 2 + 4 + · · · + 2n = k=1 M 2k IE xe k∈{1,5,7} EH BA SH Proposition uk contient n − p + 1 termes. EL n X n X re k 2 = 12 + 52 + 72 ai X • ui = u1 + u5 + u7 . i∈A k=2 Exemple 1. X de • Si A = {1, 5, 7} alors uk = u2 + u3 + u4 + u5 pl 5 X m • ar ia G H termes de la suite u pour les indices appartenant à A. ar ia G H AF k=p M Remarque. L’indice de la somme est une variable muette, ainsi n X uk = ui = i=p n X uj j=p ai re de k=p n X xe m pl Proposition (Sommes à connaître) IE Soit n ∈ N, p ∈ N tel que p ⩽ n et c ∈ R. n X c = (n − p + 1)c 1. SH BA k= k=0 M ar ia G H AF k=0 n(n + 1)(2n + 1) 6 EH k2 = EL 3. k=p n X n X n(n + 1) 2 k=0  2 n X n(n + 1) k3 = 4. 2 2. k=0 Proposition (Relation de Chasles) FE LE H BA SH k=0 IE xe m pl ai re de Attention. Il faut systématiquement mettre des parenthèses à l’intérieur d’une somme!quand elle contient n n X X uk +3 et non comme uk +3 sera interprété comme une addition ou une soustraction. Par défaut, k=0 k=0 ! n n X X uk + 3(n + 1). (uk + 3), qui vaut d’ailleurs Soient p, m, n ∈ N, avec p ⩽ m < n, et u une suite. Alors n X k=p 4 uk = m X k=p uk + n X k=m+1 uk 9 X Exemple 2. uk = 3 X uk + uk + 9 X uk k=8 k=4 k=1 k=1 7 X n X yk k=0 xe m pl ai re = k=0 n X SH (k2 − 2k) k2 − 2 BA k=0 n X n X AF EL EH k(k − 2) = IE k(k − 2). k=0 n X par linéarité de la somme k k=0 k=0 H n X xk + λ k=0 k=0 Exercice 3. Calculons n X M (xk + λyk ) = de n X Soient (xk ) et (yk ) deux suites, et λ ∈ R. Alors ar ia G H Proposition (Linéarité de la somme) G n(n + 1)(2n + 1) n(n + 1) −2 6 2 n(n + 1)(2n + 1 − 2 × 3) = 6 n(n + 1)(2n − 5) = 6 (k − 1)2 = 02 + 12 + · · · + (n − 1)2 = SH n−1 X BA n X j 2 . Quand k varie de 1 à n, j varie de 0 à n − 1. EH Intuition. IE Changements d’indices j=0 k=1 EL 2.2 xe m pl ai re de M ar ia = n+m X ia uk+m = ui ar n X M Soient n, p, m ∈ N avec p ⩽ n. Alors G H AF Proposition (Changement d’indice croissant) i=p+m de k=p xe m pl ai re On dit qu’on a effectué le changement d’indice i = k + m. BA n X (k + 1)3 = G H AF EL k=0 EH Exercice 4. Complétons : SH IE Remarque. Supposons m ⩽ p. On a également la formule ··· X ia k3 = k=1 re n−1 X n+4 X (j − 3)3 j=4 un−k = ai uj Quand k varie de 0 à n − 1, j varie j=1 xe m pl n X FE LE H BA SH IE Proposition (Changement d’indice décroissant) n X k=p n−p un−k = X uj . j=0 On dit qu’on a effectué le changement d’indice j = n − k. Exemple 3. n X k=1 (n + 2 − k)3 = n+2 X ui i=p−m (j − 3)3 k=0 Soient n, p ∈ N, p ⩽ n. Alors n−m X j=··· Intuition. un + · · · + u1 = u1 + · · · + un et donc de n à 1. ··· X n+1 X de M ar k3 = (k + 1)3 = k=0 uk−m = k=p k=··· n X n X j 3 , après avoir posé j = n + 2 − k. j=2 5 2.3 Sommes classiques G (uk+1 − uk ) = un+1 − up ar ia n X Soient n, p ∈ N, avec p ⩽ n. Alors H Proposition (Somme télescopique) (uk − uk−1 ) = un − up−1 , mais aussi n X (uk − uk+1 ) = up − un+1 . k=p k=p AF EL EH BA SH Inutile de tous les apprendre, il n’y a que deux schémas à retenir :
P • suivant - précédent = dernier - premier
P • précédent - suivant = premier - dernier ar ia G H Exercice 5. Calculons les sommes suivantes : n X 1 • k(k + 1) k=1 =1− k=1 ai re de = ln(n + 1) xe m pl Théorème (Somme géométrique) BA SH IE Soient n, p ∈ N avec p ⩽ n, et q ∈ R. Alors : n X 1 − q n−p+1 q p − q n+1 qk = qp × 1. Si q ̸= 1, = 1−q 1−q de EL M ar ia G k=p AF qk = n − p + 1 H 2. Si q = 1, n X EH k=p ai re Exercice 6. Soit n ⩾ 3. Calculons n X 1 . 2n k=3 SH IE xe m pl  3  n+1 1 1     − n n X 1 n X 1 2 2 1 1 1 1 = − = = − n. On a = 2 1 2n 2 8 2n+1 4 2 k=3 k=3 1− 2 FE LE H BA de BA EH AF H k=1 M k=1   X  X  n n k+1 1 ln [ln(k + 1) − ln(k)] = ln(n + 1) − ln(1) = = ln 1 + k k G n X  EL 1 ln 1 + k n n+1 ia k=1  ar • n X par télescopage SH = 1 n+1 re  ai 1 1 − k k+1 pl k=1  m n xe n X (k + 1) − k X 1 = = k(k + 1) k(k + 1) IE k=1 M k=1 n X xe m n X IE Remarque. On a également pl ai re de M k=p 6 par télescopage 2.4 Sommes doubles 2.4.1 Sommes doubles sur un rectangle ar ia G H Définition (Somme double sur un rectangle) de M Une somme double sur un rectangle, ou double somme rectangulaire est une somme X de la forme ui,j = u1,1 + u1,2 + · · · + u1,p + u2,1 + · · · + u2,p + · · · · · · + un,1 + · · · + un,p pl ai re 1⩽i⩽n X ui,j ou encore (i,j)∈J1,nK×J1,pK i∈J1,nK j∈J1,pK X ui,j AF EL EH Si p = n, on peut noter cette somme ui,j . SH X BA Remarque. On peut également noter IE xe m 1⩽j⩽p H 1⩽i,j⩽n i=1 1⩽i⩽n j=1 = j=1 ar ia p n X X ! ui,j i=1 M ! SH IE xe m pl 1⩽j⩽p ui,j de p n X X re ui,j = ai X G Proposition (Interversion de sommes rectangulaires) X ki i=1 = n X i n X k=1 2 H k ! de même m BA SH IE par linéarité de la somme n(n + 1) 2 xe =  pl ai i=1 ! i G k k=1 ! ia n X ar = n X M ki i=1 k=1 ! de n n X X re ki = 1⩽k,i⩽n ui,j . j=1 i=1 AF 1⩽k,i⩽n X p n X X EL Exercice 7. Calculons EH BA Remarque. Les parenthèses entre les sommes ne sont donc pas nécessaires : on peut écrire EL EH Proposition (Produit de sommes) n X i=0 ui ! m X j=0 vj ! = n X m X i=0 j=0 u i vj = m X n X vj u i j=0 i=0 xe m Sommes doubles sur un triangle FE LE H BA SH IE 2.4.2 pl ai re de M ar ia G H AF Soient u et v deux suites définies sur N, n, m ∈ N. Alors : Définition (Somme double sur un triangle) Une somme double sur un triangle, ou double somme triangulaire est une somme de la X forme ui,j = u1,1 + u1,2 + u2,2 + u1,3 + u2,3 + u3,3 + · · · + u1,n + · · · + un,n 1⩽i⩽j⩽n ou bien de la forme X ui,j = u1,2 + u1,3 + u2,3 + · · · + u1,n + · · · + un−1,n 1⩽i<j⩽n 7 Proposition (Interversion de sommes triangulaires) 1⩽i<j⩽n n−1 X i=1 n X j=i+1 = j−1 n X X j=2 ui,j i=1 H ! G ui,j ui,j i=1 ! ar ia ui,j = j=1 ! M X = ui,j j=i j n X X de 2. i=1 ! pl ai re ui,j = 1⩽i⩽j⩽n n n X X xe m 1. X IE Remarque. On retiendra ces formules de gauche à droite ainsi que de droite à gauche. Il y a donc 4 Grand indice d’abord j=1 j X ui,j i=1 ! = i=1 n X n X i=1 ui,j j=i ! i=1 j=i+1 n X j−1 X j=2 ui,j i=1 j=2 ! = n−1 X i=1 ui,j j=i+1 ! xe m pl ai re n X n X i j i=1 j=i i=1 n X H j=1 IE j n X n n X X X i X i i = = j j j i=1 j=i j=1 i=1 1⩽i⩽j⩽n BA On commence par chercher l’expression la plus simple : SH Exercice 8. Calculons j=i G n X n X ar ia i=1 Contrainte : i < j ! ! j−1 n X X ui,j = ui,j n−1 X M Petit indice d’abord Contrainte : i ⩽ j ! ! j n X X ui,j = ui,j n X de n X AF EL EH BA SH combinaisons : EH Cette dernière expression est la plus intéressante. IE xe m pl ai re de M ar ia G H AF EL j j n n n X X X X j(j + 1) 1X 1 i = × i= j j j 2 j=1 i=1 j=1 j=1 i=1 ! n n 1X 1 X = j+n (j + 1) = 2 j=1 2 j=1   n(n + 3) 1 n(n + 1) +n = = 2 2 4 BA SH Proposition (Carré de somme - HP) EH ∗ k=1 uk !2 = n X k=1 u2k + 2 X ui uj 1⩽i<j⩽n M ar ia G H AF EL Soit n ∈ N , et u une suite. Alors n X Produits pl Factorielle xe m 3.1 ai re de 3 Soit n ∈ N∗ . On appelle factorielle n, que l’on note n!, le nombre n! = n × (n − 1) × · · · × 1. Par convention, 0! = 1. FE LE H BA SH IE Définition (Factorielle) Exemple 4. 5! = 5 × 4 × 3 × 2 × 1 = 120 Remarque. On peut en mémoriser certaines : 0! = 1, 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, 6! = 720. 8 3.2 Notation et propriétés k=p G n Y uk = up × up+1 × · · · × un ar ia uk par k=p pl ai re de M n Y Soient p, n ∈ N, avec p ⩽ n, et u une suite. On définit H Définition uk = uk k=1 n Y uk k=m+1 ! AF EL EH k=1 ! IE m Y SH Soient n, m ∈ N tels que m < n, et u une suite. Alors n Y BA ∗ xe m Proposition (Relation de Chasles) G H Remarque. Les changements d’indices marchent également pour les produits. On rédige de la même M ar ia manière qu’avec les sommes. k=1 uk ai pl SH n Y uk k=1 Si de plus les vk ne s’annulent pas, on a = n Y vk BA n Y vk k=1 ! m uk k=1 n Y xe (uk vk ) = k=1 ! IE n Y EH Soit n ∈ N , u et v deux suites. Alors n Y vk EL ∗ re de Proposition ia G H AF k=1 ar p Y M (k(k + 1)) à l’aide de factorielles. de Exercice 9. Exprimons k=1 IE p+1 = p! Y k=2 k (k + 1) k=1 ! ! par changement d’indice (p + 1)! = (p!)2 (p + 1) 1 G H AF EL EH BA SH = p! p Y ai k xe k=1 ! pl (k(k + 1)) = p Y m p Y re k=1 M ar ia Proposition (Produit télescopique) re de Soient n, p ∈ N∗ , où p ⩽ n. Alors n Y un+1 uk+1 = uk up SH IE xe m pl ai k=p FE LE H BA Remarque. De même que pour les sommes, on retiendra surtout les deux schémas : Y suivant dernier • = précédent premier Y précédent premier • = suivant dernier Exercice 10. Calculons n Y ek!−(k+1)! k=1 9 n Y ek! = e e(n+1)! par télescopage H e(n+1)! (xk + λyk ) ̸= n Y xk + λ yk k=0 k=0 k=0 n Y M n Y Attention. Le produit n’est pas linéaire : ar ia G k=1 k=1 e1! = e(k+1)! de ek!−(k+1)! = pl ai re n Y n Y (λuk ) = λn uk k=1 k=1 G H k=1 n Y BA 2. AF EL EH Soit (un ) une suite, et λ ∈ R. Alors : n Y λ = λn 1. SH IE xe m Proposition IE xe k=0 k=0 SH Lien entre somme et produit BA 3.3 m pl ai re de M ar ia Attention. De même que pour les sommes, les parenthèses sont importantes. On les mettra à chaque ! fois n n Y Y uk × c uk c est ambigu car il peut signifier qu’il y a un produit dans un grand produit. Ainsi, k=0 k=0 ! n n Y Y uk × cn+1 . (uk c) = ou bien EL EH Définition (Logarithme en base quelconque - HP) ia G ln(x) ln(b) xe m pl ai Proposition (Puissance et logarithme - HP) re de M ar ∀x ∈ R∗+ , logb (x) = H AF Soit b > 1. On appelle logarithme en base b, noté logb , la fonction de R∗+ telle que EH BA SH IE Soit b > 1. Pour tout x ∈ R, logb (bx ) = x. Pour tout y ∈ R∗+ , blogb (y) = y. • Le logarithme en base e est le logarithme naturel, dit népérien, noté ln. AF EL Remarque. G H • Le logarithme en base 10 a de nombreuses applications en sciences, notamment pour le calcul des M ar ia échelles (Richter...). de • Le logarithme en base 2 est très utile en informatique car les nombres s’y écrivent en binaire (donc pl ai re en puissances de 2). Soit n ∈ N∗ et u une suite. 1. Pour tout q > 0, q Pn k=1 uk H BA SH IE xe m Proposition q uk d’où pour q = e, exp 2. Pour tout b > 1, logb n Y k=1 uk ! = n X uk k=1 k=1 LE FE = n Y n X logb (uk ) d’où pour b = e, ln ! = n Y n Y k=1 k=1 10 exp(uk ) k=1 uk ! = n X k=1 ln(uk ) 4 En Python H Méthode (Calcul de sommes et de produits) de la liste, on fait : ments de la liste, on fait : M Pour calculer le produit de tous les élé- S = 0 P = 1 for i in range(n): for i in range(n): xe m pl ai re de Pour calculer la somme de tous les éléments ar ia G Prenons une liste u comportant n éléments. AF EL EH BA SH IE P = P * u[i] S = S + u[i] Remarque. Notez que S commence à 0 tandis que P commence à 1. • P /= a signifie P = P/a M • S -= a signifie S = S - a de • P *= a signifie P = P*a xe m pl ai re • S += a signifie S = S + a ar ia G H Commandes SH IE Méthode (Calcul de double somme) S = 0 Supposons n = m. n−1 X n−1 X Pour calculer ui,j , on fait : for i in range(n): ar EH BA Prenons un tableau u comportant n × m éléments. AF EL Pour calculer la somme de tous les éléments H du tableau, on fait : G i=0 j=i M ia S = 0 de for j in range(m): for j in range(i,n): S += u[i,j] IE xe m pl ai re S += u[i,j] for i in range(n): BA SH Méthode (Définition de la factorielle) EL EH Pour définir la factorielle, on s’y prend de manière récursive. Soit n ∈ N. H AF def factorielle(n): ia G if (n==0): return 1 pl ai re de M ar else : return n*factorielle(n-1) Méthodes SH IE xe m 5 −→ Jamais par récurrence. Soit n ∈ N. Comme un+1 = ..., alors ... Mq ∀n ∈ N, ... −→ Direct, ou par récurrence si impossible. Soit (un ) définie par u0 = ... et −→ Récurrence FE LE H BA Mq un+1 = ...un un+1 = ...un . Mq ∀n, un ... 11 Soit (un ) définie par u0 = −→ Récurrence double −→ Récurrence .., u1 = .. et un+2 = ..un+1 ..un . ar ia G H Mq ∀n, un ... n X ... = ... Mq ∀n ∈ N, de pl ai re −→ Télescopage −→ Un télescopage? −→ Télescopage  Y = ln X = ln  X = exp Y = exp xe m Un télescopage? IE −→ BA SH Changer d’indice (décroissant) −→ ar ia M de re ai pl m −→ xe −→ IE −→ G H ..(k + 1) − ..k Y ... ... Y ..(k + 1) ..k X ln  Y ln Y exp  X exp X k ... X
.. + .. · k + .. · k2 X 2 uk −→ AF EL EH
Changer d’indice SH ... − ... X
−→ Somme géométrique −→ EH un−k uk−1 P P P 2 Se calcule : 1, k, k X   X  X X = ui uj = ui uj = ... −→ EL uk+1 ou i AF X j X −→ H X j i j re Blind-test m pl ai 6 de M ar ia G i X XX −→ BA XX M k=1 IE EL EH par convention ... n X Ppst : uk contient ... termes BA SH Axm : principe de récurrence double P Dfnt : = ... On la note ... (4) G H AF k=p P P P 2 P 3 Ppst : c, k, k , k M ar ia Ppst : relation de Chasles Ppst : linéarité de la somme de Ppst : changement d’indice croissant ai re Ppst : changement d’indice décroissant pl Ppst : somme télescopique (2 schémas) Ppst : interversion de sommes triang. (4) P Ppst : ( )2 = ... Dfnt : factorielle = ... Q Dfnt : = ... Ppst : relation de Chasles Q Ppst : (uk vk ) = ... FE LE H BA SH IE xe m Thm : somme géométrique (2) PP Dfnt : sur un rectangle = ... PP Ppst : = ... P P Ppst : ( ) ( ) = ... PP Dfnt : sur un triangle = ... xe Axm : principe de récurrence simple 12 Q uk = ... vk Ppst : produit télescopique (2 schémas) Q Q Ppst : λ = ... et (λuk ) = ... Dfnt : logb = ... Ppst : logb (...) = ... et b... = ... P = ... d’où ... Q logb ( ) = ... d’où ... Ppst : q Mtd : sommes et produits en Python Cmd : += etc (4) Mtd : doubles sommes en Python Mtd : déf. factorielle en Python