Récurrence et récursivité
Les suites
Une suite est une liste ordonnée d'éléments appellés "terme".
La longueur d'une suite correspond au nombre d'élements qu'elle contient. Il existes quelques noms spécifiques pour certaines suites :
- vide désigne une suite composée de 0 élements 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'élements (exemple "La suites des nombres positifs partant de 0 jusqu'a l'infini, ou la suite de Fibionacci" 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 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 notté $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éccurence
Le but de la réccurence est de montrer qu'une propriété $P(n)$ est vraie pour tout $n$.
- Premièrement, l'initialisation, qui corresponds