Suite définie par récurrence

décalage à rétroaction linéaire Le registre à décalage à rétroaction linéaire constitue l’élément de base des générateurs pseudo-aléatoires utilisés pour la génération de la suite chiffrante. Définition 1 Un registre à décalage à rétroaction linéaire binaire de longueur L est composé d’un registre à décalage contenant une suite de L bits (s i , . . . , s i +L−1) et d’une fonction de rétroaction linéaire. On l’appelle aussi par son acronyme anglais: LFSR (Linear Feedback Shift Register) 1

Capacités attendues Commentaires Suites Suites géométriques. • Reconnaître et exploiter une suite géométrique dans une situation donnée. • Connaître la formule donnant : 1 + q + K + qn avec q ≠ 1 . Limite de la suite (qn), q étant un nombre réel strictement positif. Suites arithmético-géométriques. • Déterminer la limite d’une suite géométrique de raison strictement positive. • Étant donné une suite (qn) avec 0  q  1, mettre en oeuvre un algorithme permettant de déterminer un seuil à partir

cateurs sont les mêmes : la consommation peut être modélisée par une suite géométrique. 3 b. L’augmentation est de 11 pour 1 000, ou 1,1 % par an. a. Vrai : CM − 1 = B C c. Au mois n + 1 , le montant après prélèvement est u n − 120 . La grand−mère de Nath ajoute 0,1 × ( u n − 120 ) . Le montant après le dépôt est donc : u n+1 = ( u n − 120) + 0,1 ( u n − 120 ) = ( u n − 120 ) × 1,1 . QCM – Reconnaître une suite arithmétique ou géométrique 1 a. Les dates sont espacées de la même

+ 2) (n + 3) 2 (n + 1) (n + 2) (n + 3) = (n + 1) (3 (n + 1) + 5) (n + 1) (3n + 8) ′ = = Sn+1 2 (n + 1) (n + 2) (n + 3) 2 (n + 2) (n + 3) 2 Donc Hn+1 est encore vraie. Ainsi, Hn est fondée et héréditaire, elle est donc, d’après le principe de récurrence, vraie pour tout entier n non nul. 3) (a) Une simple vérification : 1 1 k+2−k 2 − = = k k+2 k (k + 2) k (k + 2) (b) La somme Sn va, à l’aide de la décomposition précédente, devenir télescopique : n Sn = k=1 n 2 = k (k + 2) 1 − k n n

2. b. On en déduit que p n = v n + 0, 4 = p n = 0, 4 + 0, 2 × 0, 5n . n→+∞ a. On peut écrire par exemple la relation de récurrence précédente p n+1 = 0, 5p n + 0, 2 ⇐⇒ p n+1 − 0, 4 = 0, 5p n + 0, 2 − 0, 4 ⇐⇒ p n+1 − 0, 4 = 0, 5p n − 0, 2 ⇐⇒ p n+1 − 0, 4 = 0, 5 p n − 0, 4 ⇐⇒ v n+1 = 0, 5v n . Cette relation de récurrence montre que la suite (v n ) est une suite géométrique de raison 0, 5. On en déduit que v n = v 1 × 0, 5n . Or v 1 = p 1 − 0, 4 = 0, 5 − 0, 4 = 0, 1. Donc v n = 0, 2 × 0, 5n

réels) ou ℂ (corps des complexes). Une suite (u_n)_{n \in \N} à valeurs dans K est dite arithmético-géométrique s'il existe deux éléments a et b de K tels que la suite vérifie la relation de récurrence suivante : \forall n\in\N,~u_{n+1}=a u_n+b. Remarque. On peut toujours ramener l'étude d'une suite (un)n ≥ n0 à celle d'une suite (vp)p ∈ ℕ en posant vp = un0 + p1. La suite (un) vérifie une relation de la forme ci-dessus pour tout n ≥ n0 si et seulement si la suite (vp)p ∈ ℕ est arithmético-géométrique

Présentation des suites et récurrence Notion de suite : Une suite réelle est une application de N (ou parfois de N∗ ) à valeurs dans R. La suite N −→ R est notée de plusieurs façons : n −→ un (un )n∈N I , (un ) ou parfois u Suites arithmétiques et géométriques Soit n ∈ N∗ et q ∈ R\{1}. Alors 1 + 2 + 3 + ... + n = ...... ...... 1 + q + q2 + q3 + . . . + qn = ...... Suite arithmétique de raison r dénition par une relation de récurrence ......... un+1 = q × un Suite géométrique de raison

Exercices sur le raisonnement par récurrence Exercice 1 : Soit  nv la suite définie par :  0 0;1v  et 1 1 2 n n v v n      a) Prouver par récurrence la propriété P : 0 1n nv  b) Prouver que  nv est croissante. c) On pose 0 cosv   avec π 0; 2       , montrer par récurrence que cos 2 n nv        Exercice 2 : Prouver par récurrence que, 2, 2n n n    est un nombre pair. Exercice 3 : Soit la suite  nu définie par : 1 1u  et 1 , 1 n n n u

sur le raisonnement par récurrence - Corrigé 1) On considère la suite définie par Montrer que pour tout entier naturel , . Montrons par récurrence la propriété : Pour tout entier naturel , Initialisation : . La propriété est vraie pour Hérédité : Supposons qu’il existe un entier naturel tel que Conclusion : On a montré que la propriété est vraie au rang et que si vraie alors est aussi vraie. Donc pour tout entier naturel 2) On considère la suite définie pour . est par

SUITES (Partie 1) I. Raisonnement par récurrence C'est au mathématicien italien Giuseppe Peano (1858 ; 1932), ci-contre, que l'on attribue le principe du raisonnement par récurrence. Le nom a probablement été donné par Henri Poincaré (1854 ; 1912). Principe : On considère une file illimitée de dominos placés côte à côte. La règle veut que lorsqu'un domino tombe, alors il fait tomber le domino suivant et ceci à n'importe quel niveau de la file. Alors, si le premier domino tombe, on est assuré