Récurrence et récursivité
Les suites
Une suite est une liste ordonnée d'éléments appelés "terme".
La longueur d'une suite correspond au nombre d'éléments qu'elle contient. Il existe quelques noms spécifiques pour certaines suites :
- vide désigne une suite composée de 0 élé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'éléments (exemple "La suite des nombres positifs partant de 0 jusqu'à l'infini, ou la suite de 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}$. À savoir que contrairement aux suites, 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 noté $E(s)$
Note: La suite de fibionacci est une suite commençant par
0,1où chaque élément est la somme des 2 précédents.
La récurrence
Le but de la récurrence est de montrer qu'une propriété $P(n)$ est vraie pour tout $n$.
- Premièrement, l'initialisation, qui correspond