C'est une technique de raisonnement utilisée pour démontrer une propriété vérifiée par des nombres entiers. Le raisonnement par récurrence se décompose en trois étapes : l'hérédité, l'initialisation et la conclusion. Ces trois étapes devront clairement apparaître dans la rédaction.
Dans la partie sur l'hérédité, on suppose que quelque chose est vrai pour un rang \(n\) quelconque fixé puis on démontre que, sous cette hypothèse, cela se transmet au rang suivant. Ce qui est supposé (noté \(\mathbf{HR_n}\)) pourra être une propriété faisant intervenir uniquement le rang \(``n"\) ou une propriété qui porte sur \(``n"\), \(``n-1"\), \(``n-2"\), etc. On utilisera le modèle suivant :
| Étape | Rédaction |
|---|---|
| 1ère étape : l'hérédité | On suppose que pour un certain rang \(n\) fixé, on a : \(\ldots\) (c'est \(HR_n\)) On sait que \(\ldots\) Or, d'après \(HR_n\), on a \(\ldots\) Ainsi, \(\ldots\) donc \(HR_{n+1}\) est vraie. |
| 2ième étape : l'initialisation | Ici, \(H_{n_0}\) est effectivement vraie. |
| 3ième étape : la synthèse | Conclusion : D'après le théorème de récurrence, on a pour tout \(n \geq n_0\), \(HR_n\) vraie. |
Pour \(p, q\) deux entiers naturels avec \(p \leq q\) et \(a_p, a_{p+1}, \ldots, a_{q-1}, a_q\) des nombres réels, on note :
Pour \(n \in \mathbb{N}^*\), on pose :
Ainsi, \(n! = 1 \times 2 \times 3 \times \ldots \times (n-1) \times n = \prod_{k=1}^{n} k\). (\(n!\) se lit « factorielle \(n\) »)
Par convention, on pose \(\boxed{0! = 1}\).
Ainsi, on a : \(\boxed{\forall n \geq 1,\quad n! = n \times (n-1)!}\)
Dans un produit de nombres réels, on peut déplacer les termes (car \(x \times y = y \times x\)).
Ainsi, \(\forall n \in \mathbb{N}^*\) :
La bonne méthode pour compter, c'est de commencer à 1 !!!
Lorsque l'indice \(k\) varie de \(p\) à \(n\), on va donc écrire les indices manquants (ceux de 1 à \(p-1\)) :
Il y a \(n\) entiers dans \(\llbracket 1,n \rrbracket\) ; on enlève les entiers de 1 à \(p-1\) : il reste \(\boxed{n-(p-1)}\) entiers dans \(\llbracket p,n\rrbracket\).
\[x^n = \prod_{k=1}^{n} x \quad \text{(puissance entière)}\]
\[x^a = e^{a\ln(x)} \quad \text{(puissance réelle)}\]
Les règles de calculs sur les puissances entières s'étendent aux puissances réelles :
\(\forall (\alpha, \beta) \in \mathbb{R}^2\), \(\forall (x, y) \in {]0,+\infty[}^2\) on a :
car \((-x)^n = \left[(-1)\times x\right]^n = (-1)^n \times x^n\).
Soient \(n\) et \(p\) deux entiers. On note \(\binom{n}{p}\) et on lit « \(p\) parmi \(n\) » le nombre défini par :
Pour tout \(n \in \mathbb{N}\) et tout \(k \in \mathbb{N}\), on a :
- Si \(k \in \llbracket 0,n \rrbracket\) alors \(\displaystyle\binom{n}{k} = \binom{n}{n-k}\)
- Si \(n \geq 1\) et si \(k \geq 1\) alors : \(\displaystyle\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}\)
- Formule de Pascal : \(\forall n \in \mathbb{N}\) et \(\forall k \in \mathbb{N}\) \(\displaystyle\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}\)
La formule de Pascal permet de calculer la valeur des coefficients binomiaux pour des valeurs simples de \(n\) et \(k\).
| Ligne \(n\) | Triangle théorique | Valeurs numériques |
|---|---|---|
| \(n=0\) | \(\binom{0}{0}\) | 1 |
| \(n=1\) | \(\binom{1}{0}\quad\binom{1}{1}\) | 1 1 |
| \(n=2\) | \(\binom{2}{0}\quad\binom{2}{1}\quad\binom{2}{2}\) | 1 2 1 |
| \(n=3\) | \(\binom{3}{0}\quad\binom{3}{1}\quad\binom{3}{2}\quad\binom{3}{3}\) | 1 3 3 1 |
| \(n=4\) | \(\binom{4}{0}\;\cdots\;\binom{4}{4}\) | 1 4 6 4 1 |
| \(n=5\) | \(\binom{5}{0}\;\cdots\;\binom{5}{5}\) | 1 5 10 10 5 1 |
| \(n=6\) | \(\binom{6}{0}\;\cdots\;\binom{6}{6}\) | 1 6 15 20 15 6 1 |
Soient \(a_1, \ldots, a_n\) des nombres réels. La somme de ces nombres se note \(\displaystyle\sum_{k=1}^{n} a_k = a_1 + a_2 + \ldots + a_n\).
Pour tout entier \(N\), on a les formules suivantes :
| Somme | Formule |
|---|---|
| Somme des entiers | \(\displaystyle\sum_{k=0}^{N} k = \frac{N(N+1)}{2}\) |
| Somme des carrés d'entiers | \(\displaystyle\sum_{k=0}^{N} k^2 = \frac{N(N+1)(2N+1)}{6}\) |
| Somme des cubes d'entiers | \(\displaystyle\sum_{k=0}^{N} k^3 = \left(\frac{N(N+1)}{2}\right)^2\) |
Pour tout \((N, p) \in \mathbb{N}^2\) avec \(p \leq N\), et pour tout \(x \in \mathbb{R}\) avec \(x \neq 1\) :
En particulier, \(\forall x \neq 1\) et \(\forall N \in \mathbb{N}\) :
Et si \(x = 1\) alors \(\displaystyle\sum_{k=0}^{N} 1^k = N+1\).
Soient \(A\), \(B\) deux réels et \(N \in \mathbb{N}\). On a :
Soient \(A\), \(B\) deux réels. On a :
Dans une somme, on peut mettre une constante en facteur :
\[\boxed{\sum_{k=p}^{n} \text{cste} = \text{cste} \times \text{nbre de termes}}\]
Dans une somme, on peut découper la somme au niveau de la quantité à sommer :
On peut aussi découper la somme au niveau des indices :
On a : \(\displaystyle\sum_{k=1}^{n+1}(k-1)^2 = 0^2 + 1^2 + 2^2 + \ldots + n^2 = \sum_{j=0}^{n} j^2\). Ainsi, cette somme est une somme connue.
Le passage du premier \(\Sigma\) au deuxième se fait par changement d'indice : on introduit un nouvel indice \(j\) qui s'exprime en fonction de l'ancien \(k\) à l'aide d'une égalité du type \(j = k + M\) ou \(j = M - k\) (avec \(M\) entier). Ceci modifie les bornes du second \(\Sigma\).
Ce type de somme s'appelle une somme télescopique. Elles se calculent en découpant le \(\Sigma\) initial en deux \(\Sigma\) puis en faisant apparaître, par changement d'indice, la même quantité à sommer dans chacun des deux nouveaux \(\Sigma\). Pour les indices communs aux deux sommes, la quantité disparaît.
Ainsi, dans l'exemple précédent :
On fait alors apparaître la même quantité à sommer (\(1/k\) ou \(1/i\)) dans les deux \(\Sigma\). Pour les indices communs aux deux sommes (ici c'est entre 2 et \(n\)), la quantité disparaît.
On peut écrire un programme Python pour calculer la valeur d'une somme ou d'un produit. Ainsi, les instructions ci-contre permettent de calculer \(s_n = \displaystyle\sum_{k=1}^{n} \ln k\) :
def somme(n): S = 0 for k in range(1, n+1): S = S + np.log(k) # S = S + ln(k) return(S)
Les exemples suivants présentent quelques-uns des outils qui pourront nous permettre de prouver des inégalités.
On étudie le signe de la différence des deux membres de l'inégalité à démontrer.
Lorsque \(f\) est une fonction croissante sur \(I\) on a : pour tout \((a,b) \in I^2\), \[\boxed{\text{si } a \leq b \text{ alors } f(a) \leq f(b)}\]
Lorsque \(f\) est une fonction décroissante sur \(I\) on a : pour tout \((a,b) \in I^2\), \[\boxed{\text{si } a \leq b \text{ alors } f(a) \geq f(b)}\]
En effet, on peut additionner entre elles des inégalités :
On peut les multiplier entre elles si elles portent sur des nombres positifs :
Pour majorer un quotient \(\dfrac{N}{D}\) avec \(N \geq 0\) et \(D > 0\), on peut :
ex. : Montrer que \(\forall x > 2\), \[\frac{x+2}{x^2+x} \leq \frac{x+x}{x(x+1)} = \frac{2}{x+1}\]
ex. : Montrer que \(\forall x > 2\), \[\frac{x+2}{x^2+x} \leq \frac{x+2}{x} = 1 + \frac{2}{x}\]