Langage de la logique et des ensembles

Raisonnement par récurrence - Exercice 2

30 min
50
Soient aa et bb deux nombres réels et soit nn un nombre entier naturel. La formule du binôme de NewtonNewton permet de déterminer le développement de l'expression (a+b)n(a+b)^n. La formule est la suivante :
(a+b)n=∑k=0n(nk)ak bn−k(a+b)^n = \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) a^k \, b^{n-k}
Avec :
(nk)=n!k! (n−k)!\left( \begin{array}{c} n \\ k \end{array} \right) = \dfrac{n !}{k! \, (n-k)!}
Les rôle des deux réels aa et bb sont permutable. C'est par l'application du binôme de NewtonNewton, que l'on a le célèbre développement suivant :
(1+x)n=∑k=0n(nk)xk=(n0)x0+(n1)x+(n2)x2+⋯+(nn)xn(1+x)^n = \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) x^k = \left( \begin{array}{c} n \\ 0 \end{array} \right) x^0 + \left( \begin{array}{c} n \\ 1 \end{array} \right) x + \left( \begin{array}{c} n \\ 2 \end{array} \right) x^2 + \cdots + \left( \begin{array}{c} n \\ n \end{array} \right) x^n
Soit :
(1+x)n=∑k=0n(nk)xk=1+nx+12n(n−1)x2+⋯+xn(1+x)^n = \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) x^k = 1 + n x + \dfrac{1}{2} n (n-1) x^2 + \cdots + x^n

En réalité, cette formule était connue dès le dixième siècle, en particulier des mathématiciens indiens (par exemple Halayudha), arabes et perses (comme Al-Karaji) et au treizième siècle, le mathématicien chinois Yang Hui la démontra indépendamment. En 1665, Newton la généralisa à des exposants non entiers.
Question 1

Soient aa et bb deux nombres réels et soit nn un nombre entier naturel. Démontrer la formule du binôme de NewtonNewton, à savoir la formule est la suivante :
(a+b)n=∑k=0n(nk)ak bn−k(a+b)^n = \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) a^k \, b^{n-k}
Avec :
(nk)=n!k! (n−k)!\left( \begin{array}{c} n \\ k \end{array} \right) = \dfrac{n !}{k! \, (n-k)!}

Correction
Nous allons réaliser cette démonstration par récurrence.
Notons par P(n)P(n) la propriété associée à la formule du binôme de NewtonNewton pour un développement à la puissance n∈Nn \in \mathbb{N}. Donc :
P(n):(a+b)n=∑k=0n(nk)ak bn−kP(n) : (a+b)^n = \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) a^k \, b^{n-k}
▶ Etape  1:L′initialisation{\color{green}{\bf{\blacktriangleright \,Etape \,\, 1 : L'initialisation}}}
Soit n=0n=0, vérifions si la propriété P(0)P(0) est bien vérifiée. On a :
P(0):(a+b)0=∑k=00(0k)ak b0−kP(0) : (a+b)^0 = \sum_{k = 0}^0 \left( \begin{array}{c} 0 \\ k \end{array} \right) a^k \, b^{0-k}
Soit :
P(0):1=(00)a0 b0−0P(0) : 1 = \left( \begin{array}{c} 0 \\ 0 \end{array} \right) a^0 \, b^{0-0}
Soit encore :
P(0):1=1P(0) : 1 = 1
Ce qui est indéniablement vrai. Donc la propriété P(0)P(0) est bien vérifiée.
▶▶ Etape  2:La  transmission{\color{blue}{\bf{\blacktriangleright \blacktriangleright \,Etape \,\, 2 : La \,\, transmission}}}
Dans cette deuxième étape de la démonstration, nous allons supposer que la propriété P(n)P(n) est vraie, et sous cette vérité, démontrer que la propriété P(n+1)P(n+1) est également vraie. Autrement dit, nous allons démontrer que P(n)⟹P(n+1)P(n) \Longrightarrow P(n+1).
Ainsi, supposons que nous ayons bien la relation (a+b)n=∑k=0n(nk)ak bn−k(a+b)^n = \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) a^k \, b^{n-k}. Dans ce cas, déterminons l'expression de P(n+1)P(n+1). On a :
(a+b)n+1=(a+b)(a+b)n(a+b)^{n+1} = (a+b) (a+b)^n
Comme la propriété P(n)P(n) est supposée vraie, on a alors :
(a+b)n+1=(a+b)∑k=0n(nk)ak bn−k(a+b)^{n+1} = (a+b) \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) a^k \, b^{n-k}
En développant :
(a+b)n+1=a∑k=0n(nk)ak bn−k+b∑k=0n(nk)ak bn−k(a+b)^{n+1} = a \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) a^k \, b^{n-k} + b \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) a^k \, b^{n-k}
Donc :
(a+b)n+1=∑k=0n(nk)aak bn−k+∑k=0n(nk)ak bbn−k(a+b)^{n+1} = \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) aa^k \, b^{n-k} + \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) a^k \, bb^{n-k}
Ce qui nous donne naturellement :
(a+b)n+1=∑k=0n(nk)ak+1 bn−k+∑k=0n(nk)ak bn−k+1(a+b)^{n+1} = \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) a^{k+1} \, b^{n-k} + \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) a^k \, b^{n-k+1}
Au sein de la première somme, on pose i=k+1i = k+1. Ainsi l'indice ii débute à 11 et se termine à n+1n+1. On trouve alors :
(a+b)n+1=∑i=1n+1(ni−1)ai−1+1 bn−(i−1)+∑k=0n(nk)ak bn−k+1(a+b)^{n+1} = \sum_{i = 1}^{n+1} \left( \begin{array}{c} n \\ i-1 \end{array} \right) a^{i-1+1} \, b^{n-(i-1)} + \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) a^k \, b^{n-k+1}
Soit encore :
(a+b)n+1=∑i=1n+1(ni−1)ai bn−i+1+∑k=0n(nk)ak bn−k+1(a+b)^{n+1} = \sum_{i = 1}^{n+1} \left( \begin{array}{c} n \\ i-1 \end{array} \right) a^{i} \, b^{n-i+1} + \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) a^k \, b^{n-k+1}
Toujours dans la première somme, l'indice de sommation ii est un indice, dit, discret. Cela signifie que s'il changeait de dénomination, c'est à dire substituer à ii une autre lettre, cela ne changerai en rien l'expression de cette première somme. Pour être plus en adéquation avec la seconde somme, et que l'expression devienne manipulable plus facilement, nous allons remplacer l'indice ii par kk. Ainsi, nous obtenons :
(a+b)n+1=∑k=1n+1(nk−1)ak bn−k+1+∑k=0n(nk)ak bn−k+1(a+b)^{n+1} = \sum_{k = 1}^{n+1} \left( \begin{array}{c} n \\ k-1 \end{array} \right) a^{k} \, b^{n-k+1} + \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) a^k \, b^{n-k+1}
Afin que les deux sommes débutent à i=1i=1 et se terminent à i=ni=n, nous allons isoler le dernier terme de la première somme (celui d'indice k=n+1k=n+1), et le premier terme de la seconde somme (celui d'indice k=0k=0). Ainsi, on obtient :
(a+b)n+1=(nn+1−1)an+1 bn−(n+1)+1+∑k=1n(nk−1)ak bn−k+1+(n0)a0 bn−0+1+∑k=1n(nk)ak bn−k+1(a+b)^{n+1} = \left( \begin{array}{c} n \\ n+1-1 \end{array} \right) a^{n+1} \, b^{n-(n+1)+1} + \sum_{k = 1}^{n} \left( \begin{array}{c} n \\ k-1 \end{array} \right) a^{k} \, b^{n-k+1} + \left( \begin{array}{c} n \\ 0 \end{array} \right) a^0 \, b^{n-0+1} + \sum_{k = 1}^n \left( \begin{array}{c} n \\ k \end{array} \right) a^k \, b^{n-k+1}
Ce qui nous donne :
(a+b)n+1=(nn)an+1 b0+∑k=1n(nk−1)ak bn−k+1+(n0)a0 bn+1+∑k=1n(nk)ak bn−k+1(a+b)^{n+1} = \left( \begin{array}{c} n \\ n \end{array} \right) a^{n+1} \, b^{0} + \sum_{k = 1}^{n} \left( \begin{array}{c} n \\ k-1 \end{array} \right) a^{k} \, b^{n-k+1} + \left( \begin{array}{c} n \\ 0 \end{array} \right) a^0 \, b^{n+1} + \sum_{k = 1}^n \left( \begin{array}{c} n \\ k \end{array} \right) a^k \, b^{n-k+1}
En factorisant les deux sommes on obtient :
(a+b)n+1=(nn)an+1 b0+∑k=1n((nk−1)+(nk))ak bn−k+1+(n0)a0 bn+1(a+b)^{n+1} = \left( \begin{array}{c} n \\ n \end{array} \right) a^{n+1} \, b^{0} + \sum_{k = 1}^{n} \left( \left( \begin{array}{c} n \\ k-1 \end{array} \right) + \left( \begin{array}{c} n \\ k \end{array} \right) \right) a^{k} \, b^{n-k+1} + \left( \begin{array}{c} n \\ 0 \end{array} \right) a^0 \, b^{n+1}
Déterminons l'expression de (nk−1)+(nk)\left( \begin{array}{c} n \\ k-1 \end{array} \right) + \left( \begin{array}{c} n \\ k \end{array} \right) . On a :
(nk−1)+(nk)=n!(k−1)! (n−(k−1))!+n!k! (n−k)!\left( \begin{array}{c} n \\ k-1 \end{array} \right) + \left( \begin{array}{c} n \\ k \end{array} \right) = \dfrac{n !}{(k-1)! \, (n-(k-1))!} + \dfrac{n !}{k! \, (n-k)!}
D'où :
(nk−1)+(nk)=n!(k−1)! (n−k+1)!+n!k! (n−k)!\left( \begin{array}{c} n \\ k-1 \end{array} \right) + \left( \begin{array}{c} n \\ k \end{array} \right) = \dfrac{n !}{(k-1)! \, (n-k+1)!} + \dfrac{n !}{k! \, (n-k)!}
Ou encore :
(nk−1)+(nk)=n! kk(k−1)! (n−k+1)(n−k)!+n!k! (n−k)!\left( \begin{array}{c} n \\ k-1 \end{array} \right) + \left( \begin{array}{c} n \\ k \end{array} \right) = \dfrac{n ! \,k}{k(k-1)! \, (n-k+1)(n-k)!} + \dfrac{n !}{k! \, (n-k)!}
Donc :
(nk−1)+(nk)=n! kk! (n−k+1)(n−k)!+n!k! (n−k)!\left( \begin{array}{c} n \\ k-1 \end{array} \right) + \left( \begin{array}{c} n \\ k \end{array} \right) = \dfrac{n ! \,k}{k! \, (n-k+1)(n-k)!} + \dfrac{n !}{k! \, (n-k)!}
Par factorisation :
(nk−1)+(nk)=n!k! (n−k)!(kn−k+1+1)\left( \begin{array}{c} n \\ k-1 \end{array} \right) + \left( \begin{array}{c} n \\ k \end{array} \right) = \dfrac{n !}{k! \, (n-k)!} \left( \dfrac{k}{n-k+1} + 1 \right)
Ainsi, en réduisant au même dénominateur l'expression entre parenthèses, on obtient :
(nk−1)+(nk)=n!k! (n−k)!(k+n−k+1n−k+1)\left( \begin{array}{c} n \\ k-1 \end{array} \right) + \left( \begin{array}{c} n \\ k \end{array} \right) = \dfrac{n !}{k! \, (n-k)!} \left( \dfrac{k+n-k+1}{n-k+1} \right)
On a alors :
(nk−1)+(nk)=n!k! (n−k)!(n+1n−k+1)=(n+1)×n!k!×(n−k+1)×(n−k)!\left( \begin{array}{c} n \\ k-1 \end{array} \right) + \left( \begin{array}{c} n \\ k \end{array} \right) = \dfrac{n !}{k! \, (n-k)!} \left( \dfrac{n+1}{n-k+1} \right) = \dfrac{(n+1) \times n !}{k! \times (n-k+1) \times (n-k)!}
Ce qui nous donne :
(nk−1)+(nk)=(n+1)!k!×(n−k+1)!=(n+1)!k!×(n+1−k)!\left( \begin{array}{c} n \\ k-1 \end{array} \right) + \left( \begin{array}{c} n \\ k \end{array} \right) = \dfrac{(n+1) !}{k! \times (n-k+1)!} = \dfrac{(n+1) !}{k! \times (n+1 - k)!}
Finalement, on obtient :
(nk−1)+(nk)=(n+1k)\left( \begin{array}{c} n \\ k-1 \end{array} \right) + \left( \begin{array}{c} n \\ k \end{array} \right) = \left( \begin{array}{c} n+1 \\ k \end{array} \right)
Donc, en remplaçant ceci, on trouve que que :
(a+b)n+1=(nn)an+1 b0+∑k=1n(n+1k)ak bn−k+1+(n0)a0 bn+1(a+b)^{n+1} = \left( \begin{array}{c} n \\ n \end{array} \right) a^{n+1} \, b^{0} + \sum_{k = 1}^{n} \left( \begin{array}{c} n+1 \\ k \end{array} \right) a^{k} \, b^{n-k+1} + \left( \begin{array}{c} n \\ 0 \end{array} \right) a^0 \, b^{n+1}
Ou encore :
(a+b)n+1=(nn)an+1 b0+∑k=1n(n+1k)ak bn+1−k+(n0)a0 bn+1(a+b)^{n+1} = \left( \begin{array}{c} n \\ n \end{array} \right) a^{n+1} \, b^{0} + \sum_{k = 1}^{n} \left( \begin{array}{c} n+1 \\ k \end{array} \right) a^{k} \, b^{n+1-k} + \left( \begin{array}{c} n \\ 0 \end{array} \right) a^0 \, b^{n+1}
Cependant, on remarque que (nn)=(n+1n+1)=1\left( \begin{array}{c} n \\ n \end{array} \right) = \left( \begin{array}{c} n+1 \\ n+1 \end{array} \right) = 1. Donc :
(a+b)n+1=(n+1n+1)an+1 b0+∑k=1n(n+1k)ak bn+1−k+(n0)a0 bn+1(a+b)^{n+1} = \left( \begin{array}{c} n+1 \\ n+1 \end{array} \right) a^{n+1} \, b^{0} + \sum_{k = 1}^{n} \left( \begin{array}{c} n+1 \\ k \end{array} \right) a^{k} \, b^{n+1-k} + \left( \begin{array}{c} n \\ 0 \end{array} \right) a^0 \, b^{n+1}
Puis, on constate également que (n0)=(n+10)=1\left( \begin{array}{c} n \\ 0 \end{array} \right) = \left( \begin{array}{c} n+1 \\ 0 \end{array} \right) = 1, d'où :
(a+b)n+1=(n+1n+1)an+1 b0+∑k=1n(n+1k)ak bn+1−k+(n+10)a0 bn+1(a+b)^{n+1} = \left( \begin{array}{c} n+1 \\ n+1 \end{array} \right) a^{n+1} \, b^{0} + \sum_{k = 1}^{n} \left( \begin{array}{c} n+1 \\ k \end{array} \right) a^{k} \, b^{n+1-k} + \left( \begin{array}{c} n+1 \\ 0 \end{array} \right) a^0 \, b^{n+1}
On peut donc, maintenant, réunir ces trois termes dans la même somme. En effet, le premier terme est celui d'indice k=n+1k=n+1 et le troisième celui d'indice k=0k=0. Donc :
(a+b)n+1=∑k=1n+1(n+1k)ak bn+1−k(a+b)^{n+1} = \sum_{k = 1}^{n+1} \left( \begin{array}{c} n+1 \\ k \end{array} \right) a^{k} \, b^{n+1-k}
On constate alors que la propriété P(n+1)P(n+1) est donc bien vérifiée. On a donc bien démontré que P(n)⟹P(n+1)P(n) \Longrightarrow P(n+1).
▶▶▶ Etape  3:La  conclusion{\color{red}{\bf{\blacktriangleright \blacktriangleright \blacktriangleright \,Etape \,\, 3 : La \,\, conclusion}}}
En vertu des axiomes de la récurrence, la propriété P(n):(a+b)n=∑k=0n(nk)ak bn−kP(n) : (a+b)^n = \sum_{k = 0}^n \left( \begin{array}{c} n \\ k \end{array} \right) a^k \, b^{n-k} est vraie pour tout entier naturel nn. ■{\color{red}{\blacksquare}}