Dans certains contextes, logique mathématique (La logique mathématique, ou logique formelle, est une discipline des mathématiques qui... ) ou en informatique (L´informatique - contraction d´information et automatique - est le domaine... ), pour des structures de nature arborescente ou ayant trait aux termes du langage formel (Dans de nombreux contextes (scientifique, légal, etc. ), on désigne par langage formel un... ) sous-jacent, on parle de récurrence structurelle. On parle communément de récurrence dans un contexte lié mais différent, celui des définitions par récurrence de suites (ou d'opérations) à argument entier. Si l'unicité de telles suites se démontre bien par récurrence, leur existence, qui est le plus souvent tacitement admise dans le secondaire, voire les premières années universitaires, repose sur un principe différent. Récurrence simple sur les entiers Pour démontrer une propriété portant sur tous les entiers naturels, comme par exemple la formule du binôme ( en mathématique, binôme, une expression algébrique; voir aussi binôme de Newton... ) de Newton, on peut utiliser un raisonnement par récurrence.
\quad(HR)$$Démontrons alors qu'elle est vraie pour k + 1. Pour cela, regardons le membre de gauche au rang k + 1: $$(1+x)^{k+1} = (1+x)^k \times (1+x). $$Si je l'écris ainsi, c'est pour faire apparaître le membre de gauche de la propriété au rang k. Comme ça, je peux me servir de l'hypothèse de récurrence (HR). En effet, $$\begin{align}(1+x)^k > 1+kx & \Rightarrow (1+x)^k\times(1+x) > (1+kx)(1+x)\\& \Rightarrow (1+x)^{k+1}>1+(k+1)x+kx^2\\&\Rightarrow (1+x)^{k+1} > 1+(k+1)x. \end{align}$$ La dernière inégalité est possible car 1 +( k +1) x + kx ² > 1 + ( k +1) x; en effet, k >0 et x ²>0. Nous avons alors démontré l'hérédité. La propriété est donc vraie pour tout n >1. Le raisonnement par récurrence: étude de suites On retrouve très souvent le raisonnement par récurrence dans les études des suites de la forme \(u_{n+1} = f(u_n)\). Prenons l'exemple de \(f(x)=\frac{5-4x}{1-x}\), que l'on va définir sur [2;4]. On définit alors la suite \((u_n)\) par son premier terme \(u_0=2\) et par la relation \(u_{n+1}=f(u_n)\), c'est-à-dire:$$u_{n+1}=\frac{5-4u_n}{1-u_n}.
conclusion: la propriété $P_n$ est vraie pour tout $n\geq 1$. Il ne faut pas oublier l'initialisation! On peut prouver que la propriété $P_n$: "$3$ divise $4^n+1$" est héréditaire.... mais toujours fausse! Il existe toute une variété de raisonnement par récurrence: les récurrences doubles: on procède 2 par 2, c'est-à-dire que l'on prouve que $P_0$ et $P_1$ sont vraies, et on suppose que $P_n$, $P_{n+1}$ sont vraies pour prouver que $P_{n+1}$ et $P_{n+2}$ sont vraies. les récurrences descendantes: on prouve qu'à un certain rang $k$, $P_k$ est vraie, et on montrer que si $P_n$ est vraie, alors $P_{n-1}$ est vraie. Alors les propriétés $P_0, \dots, P_k$ sont vraies! C'est à Pascal que l'on doit la première utilisation du raisonnement par récurrence, dans le Traité du triangle arithmétique. Ses correspondances permettent même de dater la découverte avec précision, entre le 29 juillet et le 29 aout 1654. Pour Poincaré, le raisonnement par induction est LE raisonnement mathématique par excellence.
Théorème. Pour tout entier naturel $n\geqslant n_0$, on considère la proposition logique $P_n$ dépendant de l'entier $n. $ Pour démontrer que « Pour tout entier $n\geqslant n_0$, $P_{n_0}$ est vraie » il est équivalent de démontrer que: 1°) $P_{n_0}$ est vraie [ Initialisation]; 2°) Pour tout entier $n\geqslant n_0$: [$P_{n}\Rightarrow P_{n+1}$] [ Hérédité]. 3. Exercices résolus Revenons à notre exemple n°1. Exercice résolu n°2. (Facile) Démontrer que pour tout entier naturel n, on a: $2^n> n$. Exercice résolu n°3. Soit $a$ un nombre réel strictement positif. Démontrer que pour tout entier naturel n, on a: $(1+a)^n\geqslant 1+na$. Cette inégalité s'appelle Inégalité de Bernoulli. Exemple 4. Démontrez que pour tout entier non nul $n$, la somme des n premiers nombres entiers non nuls, est égale à $\dfrac{n(n+1)}{2}$. Exercice résolu 4. 4. Exercices supplémentaires pour progresser Exercice 5. Démontrez que pour tout entier naturel $n$: « $7^{2n}-1$ est un multiple de $5$ ». Exercice 6. Démontrez que pour tout entier naturel $n$: « $\dsum_{k=0}^{k=n} k^2 =\dfrac{n(n+1)(2n+1)}{6}$ ».
A l'aide d'une calculatrice ou d'un algorithme, vérifiez si ces nombres sont premiers ou non. Que constatez-vous? En 1640, le mathématicien français Pierre de Fermat a émis la conjecture que « pour tout $n\in\N$, $F_n$ est un nombre premier ». Il s'avère que cette conjecture est fausse. Presque un siècle plus tard en 1732, le premier à lui porter la contradiction, est le mathématicien suisse Leonhard Euler en présentant un diviseur (donc deux diviseurs au moins) de $F_5$ prouvant qu'« il existe au moins un nombre de Fermat qui n'est pas premier ». Il affirme que $F_5$ est divisible par 641. Blaise Pascal, à 19 ans, en 1642 invente la première ( calculatrice) qu'il appelait la « Pascaline » ou « machine arithmétique ». [Musée Lecoq à Clermont Ferrand]. Mais, existe-il un moyen de démontrer qu'une propriété dépendant d'un entier $n$, est vraie pour tout $n\in\N$ sans passer par la calculatrice? 1. 2. Étude d'un exemple Exercice résolu 1. Démontrer que pour tout entier naturel $n$, « $4^n +5$ est un multiple de $3$ ».