Démonstrations par récurrence et méthode combinatoire : vrai ou faux et Memory

La récurrence nécessite un cas de base.

Vrai — La démonstration par récurrence commence toujours par vérifier un cas initial (le cas de base).

Pour prouver P(n) on peut montrer P(1) puis \(P(n)\Rightarrow P(n+1)\).

Vrai — Montrer le cas de base et le pas inductif donne, par principe de récurrence, P(n) pour tout n≥1.

Dans l'exemple, \(1+2+\dots+n=\frac{n(n+1)}{2}\) pour tout entier \(n\ge 1\).

Vrai — Le cours montre le cas de base n=1 puis le passage de n à n+1 vérifiant l'identité pour tout n≥1.

Le pas inductif consiste à supposer \(P(n)\) et prouver \(P(n+1)\).

Vrai — C'est précisément l'étape où l'on utilise l'hypothèse de récurrence pour obtenir la propriété au rang suivant.

La formule des combinaisons est \(\binom{n}{k}=\frac{n!}{k!(n-k)!}\).

Vrai — Le cours donne cette formule standard pour le nombre de façons de choisir k éléments parmi n.

L'identité de Pascal est \(\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\).

Vrai — Le cours présente cette identité qui décompose le choix selon l'appartenance d'un élément.

On peut utiliser la méthode combinatoire pour établir des identités combinatoires.

Vrai — Le cours indique que compter des ensembles de deux façons différentes conduit à des identités.

Pour \(n=5\), \(\binom{5}{3}=10\).

Vrai — Le cours calcule \(\binom{5}{3}=\frac{5!}{3!2!}=10\) comme exemple explicite.

La méthode combinatoire consiste à décomposer un ensemble en sous-ensembles pour compter.

Vrai — C'est la technique décrite dans le cours pour faciliter le dénombrement d'objets.

Il faut vérifier que la formule utilisée est applicable dans le contexte.

Vrai — Le cours met en garde contre l'utilisation de formules sans vérifier leurs conditions d'application.

La base de récurrence est toujours \(n=0\).

Faux — Faux : le cas de base dépend du problème; dans l'exemple du cours le cas de base est \(n=1\).

Montrer que \(P(n+1)\) est vrai suffit pour conclure que \(P(n)\) est vrai pour tout n.

Faux — Ceci inverse le sens du pas inductif et ne permet pas d'établir la propriété pour les petits n.

On peut omettre de vérifier l'hypothèse de récurrence pendant le pas inductif.

Faux — Faux : le pas inductif repose sur l'utilisation explicite de l'hypothèse de récurrence \(P(n)\).

La formule \(\binom{n}{k}=\frac{n!}{k!(n-k)!}\) s'applique sans problème pour \(n<k\).

Faux — Faux : pour \(n<k\) les factorielles donnent une expression non définie dans le contexte usuel, il faut préciser la convention (souvent \(\binom{n}{k}=0\)).

L'identité de Pascal s'écrit \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k+1}\).

Faux — Faux : le second terme doit être \(\binom{n-1}{k-1}\), pas \(\binom{n-1}{k+1}\).

La somme \(1+2+\dots+n\) vaut \(\frac{n(n-1)}{2}\).

Faux — Faux : la formule correcte, montrée par récurrence dans le cours, est \(\frac{n(n+1)}{2}\).

Factoriser \(\frac{n(n+1)}{2}+(n+1)\) donne \((n+1)\frac{n}{2}\).

Faux — Faux : le bon résultat est \((n+1)\frac{n+2}{2}\) après factorisation.

Montrer seulement le cas de base suffit pour une démonstration par récurrence.

Faux — Faux : il faut aussi établir le pas inductif pour propager la propriété à tous les n.

La méthode combinatoire ne sert qu'à compter et ne permet pas de démontrer des identités.

Faux — Faux : le cours précise que la méthode combinatoire permet également d'établir des identités en comptant de deux façons.

Dans l'exemple de démonstration par récurrence, on a vérifié le cas de base pour \(n=2\).

Faux — Faux : l'exemple vérifie explicitement le cas de base pour \(n=1\).