Chap 2 - Recurrence, Sums, Products (PDF)

d pl ai re IA N R C Chapitre 2 – Récurrence, sommes et produits O Ex em ———————————————————————– Ly am M U ———————————————————————– M U R C IA N O Ex em pl ai re de ECG1 - Antoine Lagarde de Ly am Table des matières 2 ai re 1 Principe de récurrence Récurrence simple ....

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