Méthodes de raisonnement mathématique

Pour montrer $P \Rightarrow Q$ par contraposée, que doit-on démontrer ?

La contraposée de $P \Rightarrow Q$ est $\overline{Q} \Rightarrow \overline{P}$, logiquement équivalente à l'implication de départ.

Dans une preuve par l'absurde de $P$, que suppose-t-on au départ ?

Le raisonnement par l'absurde suppose la négation de ce qu'on veut démontrer, $\overline{P}$, et cherche à en tirer une contradiction logique, ce qui permet de conclure que $P$ est vraie.

Quelles sont les deux étapes obligatoires d'une preuve par récurrence simple ?

Le principe de récurrence repose sur la vérification de l'initialisation (la propriété est vraie au premier rang) et de l'hérédité (la propriété se transmet d'un rang au suivant), ce qui permet de conclure pour tous les rangs.

Vrai ou faux : la méthode d'analyse-synthèse sert à prouver l'existence et l'unicité d'un objet mathématique.

Vrai. L'analyse détermine la forme nécessaire du candidat (donnant l'unicité), et la synthèse vérifie que ce candidat satisfait bien toutes les conditions (donnant l'existence).

Pour démontrer "$\forall n \in \mathbb{N}$, $n$ pair ou $n$ impair $\Rightarrow \ldots$" en distinguant les deux cas, quelle méthode utilise-t-on ?

Découper la preuve selon que $n$ est pair ou impair (les deux cas étant exhaustifs et s'excluant mutuellement) est l'exemple typique d'un raisonnement par disjonction de cas.

Pourquoi la preuve de l'irrationalité de $\sqrt{2}$ utilise-t-elle un raisonnement par l'absurde ?

"$\sqrt{2}$ est irrationnel" signifie "$\sqrt{2}$ n'est pas de la forme $p/q$" : c'est un énoncé négatif, sans prise directe pour une construction. Supposer le contraire (existence d'une fraction irréductible $p/q=\sqrt 2$) donne au contraire des objets concrets ($p$, $q$) sur lesquels raisonner jusqu'à la contradiction.

Soit $u_0=2$ et $u_{n+1}=\sqrt{2u_n}$. On veut montrer $0 < u_n \leq 2$ pour tout $n$. Que doit-on vérifier à l'étape d'hérédité ?

L'hérédité d'une récurrence simple consiste à montrer que si la propriété est vraie au rang $n$ (hypothèse de récurrence $0<u_n\leq 2$), alors elle est vraie au rang $n+1$ ($0<u_{n+1}\leq 2$). C'est exactement l'implication de l'option A.

Vrai ou faux : dans une récurrence forte, on peut utiliser l'hypothèse $P(n)$ seule pour démontrer $P(n+1)$, exactement comme en récurrence simple.

Faux (ou du moins incomplet) : la récurrence forte autorise à utiliser toutes les hypothèses $P(n_0), \ldots, P(n)$, pas seulement la dernière. C'est une hypothèse plus riche que la récurrence simple, utile quand la relation de récurrence dépend de plusieurs termes antérieurs (comme la suite de Fibonacci).

Pour prouver par contraposée que "$n^2$ impair $\Rightarrow$ $n$ impair", que doit-on démontrer ?

La contraposée de "$n^2$ impair $\Rightarrow$ $n$ impair" est "non($n$ impair) $\Rightarrow$ non($n^2$ impair)", c'est-à-dire "$n$ pair $\Rightarrow$ $n^2$ pair".

Dans l'étape d'analyse de la décomposition $f = g+h$ (paire + impaire), que fait-on exactement ?

L'analyse part de l'hypothèse qu'un objet vérifiant les conditions existe et en déduit, par implications nécessaires, sa forme explicite — ici $g(x)=\frac{f(x)+f(-x)}{2}$ et $h(x)=\frac{f(x)-f(-x)}{2}$. Vérifier que ce candidat convient est l'étape de synthèse (option B), qui vient après.

Démontrer par récurrence que pour tout $n \in \mathbb{N}$, $4^n - 1$ est divisible par $3$.

Initialisation ($n=0$) : $4^0 - 1 = 1-1 = 0 = 3 \times 0$, qui est bien divisible par $3$.

Hérédité : supposons que $4^n - 1$ est divisible par $3$, c'est-à-dire qu'il existe $k \in \mathbb{Z}$ tel que $4^n - 1 = 3k$ (hypothèse de récurrence), donc $4^n = 3k+1$. Montrons que $4^{n+1}-1$ est divisible par $3$ :

Conclusion : par le principe de récurrence, $4^n - 1$ est divisible par $3$ pour tout $n \in \mathbb{N}$. $\square$

Soit $n \geq 2$ un entier. Vrai ou faux : pour montrer que tout entier $n\geq 2$ admet un diviseur premier, on peut raisonner par récurrence forte en utilisant, pour traiter le cas où $n$ n'est pas premier, l'hypothèse de récurrence appliquée à un diviseur strict de $n$ supérieur ou égal à $2$.

Vrai. Si $n$ est premier, $n$ est son propre diviseur premier. Si $n$ n'est pas premier, $n=ab$ avec $2\leq a < n$ ; comme $a < n$, l'hypothèse de récurrence forte (valable pour tous les rangs $2,\ldots,n-1$) s'applique à $a$, qui admet donc un diviseur premier, qui divise aussi $n$. C'est un exemple typique où la récurrence forte est nécessaire (le rang $n-1$ seul ne suffit pas, $a$ pouvant être bien plus petit que $n-1$).

Démontrer par l'absurde que pour tout entier $n \geq 2$, $n$ n'est pas à la fois pair et premier, sauf $n=2$. Plus précisément, montrer que si $n$ est premier et $n \neq 2$, alors $n$ est impair.

Raisonnement par l'absurde. Soit $n$ premier avec $n \neq 2$. Supposons, par l'absurde, que $n$ est pair : il existe $k \in \mathbb{Z}$ tel que $n = 2k$.

Comme $n \geq 2$ et $n \neq 2$, on a $n \geq 3$, donc $n$ est pair et $\geq 4$ (le plus petit pair $\geq 3$ qui n'est pas $2$), donc $k = n/2 \geq 2$.

On a alors $2 \mid n$ avec $2 \neq 1$ et $2 \neq n$ (car $n \geq 4 > 2$). Le nombre $2$ est donc un diviseur de $n$ strictement compris entre $1$ et $n$, ce qui contredit la définition de $n$ premier (un nombre premier n'a que $1$ et lui-même comme diviseurs positifs).

Cette contradiction montre que l'hypothèse "$n$ est pair" est fausse : donc $n$ est impair. $\square$

On définit $u_0=1$, $u_1=3$ et $u_{n+2}=3u_{n+1}-2u_n$. Pour montrer par récurrence que $u_n=2^{n+1}-1$ pour tout $n\in\mathbb{N}$, combien de rangs d'initialisation sont nécessaires, et pourquoi ?

La relation $u_{n+2}=3u_{n+1}-2u_n$ relie un terme à ses deux prédécesseurs immédiats $u_{n+1}$ et $u_n$. L'étape d'hérédité ne peut donc démarrer qu'à partir du rang où les deux prédécesseurs sont connus, ce qui impose d'initialiser les deux premiers rangs : $u_0 = 2^{0+1}-1 = 1$ (vrai par définition) et $u_1 = 2^{1+1}-1 = 3$ (vrai par définition). On vérifie ensuite l'hérédité : si $u_n=2^{n+1}-1$ et $u_{n+1}=2^{n+2}-1$, alors $u_{n+2} = 3(2^{n+2}-1) - 2(2^{n+1}-1) = 3\cdot 2^{n+2} - 2^{n+2} - 3 + 2 = 2\cdot 2^{n+2} - 1 = 2^{n+3}-1$, ce qui est bien la formule au rang $n+2$. Une relation d'ordre $2$ nécessite donc toujours $2$ initialisations.

Vrai ou faux : le raisonnement par contraposée et le raisonnement par l'absurde sont deux méthodes strictement identiques.

Faux. La contraposée prouve $P\Rightarrow Q$ en démontrant directement $\overline{Q}\Rightarrow\overline{P}$ (sans jamais supposer $P$). L'absurde prouve une proposition $P$ en supposant $\overline P$ et en l'associant à d'autres hypothèses déjà établies pour atteindre une contradiction quelconque (pas nécessairement $\overline P$ lui-même) ; le raisonnement par l'absurde est plus général et ne se limite pas aux implications.