Récurrence et récursivité

Les suites

Une suite est une liste ordonnée d'éléments appelléappelés "terme".

La longueur d'une suite correspond au nombre d'élementsléments qu'elle contient. Il existesexiste quelques noms spécifiques pour certaines suites :

• vide désigne une suite composée de 0 élementsléments et est représentée ainsi : $()$
• couple désigne une suite composée de 2 éléments (exemple $(1,2)$)
• finie désigne une suite composée d'un nombre déterminé d'éléments (exemple Les nombres entre 1 (inclus) et 3 (inclus) : $(1,2,3)$)
• infinie désigne une suite composée d'un nombre indéterminé d'élementsléments (exemple "La suitessuite des nombres positifs partant de 0 jusqu'aà l'infini, ou la suite de Fibionacci"Fibonacci" qui peuvent être représentée par une formule mathématique ou par une suite terminée par ... $(1,2,3,..., n)$

Une suite est notée avec des parenthèses et ne doit pas être confondue avec un ensemble qui est représenté par des accolades.

Une suite peut être transformée en ensemble en retirant tous les doublons qu'elle contient.

Ainsi la suite $(1,2,3,4,3,2)$ deviendra l'ensemble ${1,2,3,4}$. AÀ savoir que contrairement aux suitessuites, l'ordre ne compte pas dans un ensemble. Ce qu'il peut exister un nombre infini de suites pour un ensemble donné. L'ensemble correspondant à une suite est notténoté $E(s)$

Note: La suite de fibionacci est une suite commençant par 0,1 où chaque élément est la somme des 2 précédents.

La récurrence

Le but de la réccurencecurrence est de montrer qu'une propriété $P(n)$ est vraie pour tout $n$.

• Premièrement, l'initialisation, qui corresponds dsq ezajeoizajeza la magiecorrespond