Nombresentiersnaturels –Combinatoire
COURS
9
Montrons l’unicité :
Supposonsque n = 2
p
(2q +1)=2
p
(2q
+1).
Si p p
, 2
p−p
(2q +1 ) = 2 q
+1 . Le second
membre étanti mpair, le premier doit l’être aussi ;
d’où p = p
. Il reste 2q +1 = 2 q
+1;d ’où
q = q
.
Remarque :Onvient de mettre en évidence unebijection
de N
∗
dans N
2
.
1.4 • Suites définies par récurrence
Soit E un ensemble quelconque. On appelle suite d’éléments de E uneapplication de N (ou parfois d’une partie de N)d ans E. L’imagedel’entier n est
noté u n . La suite tout entière est notée (u n )( ne pas oublier les parenthèses).
Une suite peut être définie par son premier terme, parexemple u 0 , et une relation
donnant chaque terme en fonctiond up récédent : u n+1 = f (u n ). Le théorème
de récurrence permet d’affirmer l’existence et l’unicité d’une suite vérifiant ces
conditions ;o nd it que la suite estd éfinie par récurrence, ou que c’est une suite
récurrente.
IMPORTANT
La notation i n’est qu’un intermédiaire permettant de décrire la somme
ou le produit;elle n’apparaît pas dans
le résultat. On dit que c’est une variable muette.
n
i=1
ui et
n
j=1
uj représentent exactement la même chose.
Exemples :
La somme S n =
n
i=1
u i est définiepar S 0 = 0e tpour tout n ∈ N :
S n+1 = S n + u n+1 . Par exemple
n
i=1
i =
n(n +1)
2
.
De même, le produit P n =
n
i=1
u i est défini par P 0 = 1e tpour tout n ∈ N :
P n+1 = P n ×u n+1 . Par exemple : n! =
n
i=1
i.
APPLICATION 3
Changement d’indice dansune somme
Simplifierl’expression :S n =
n
p = 1
1
p
−
1
p+1
.
On peut séparer la somme en deux termes :
S n =
n
p=1
1
p
−
n
p=1
1
p +1
Dans le second terme, effectuons le changement d’indice q = p +1:
S n =
n
p = 1
1
p
−
n +1
q=2
1
q
D’aprèsl ar emarque ci-dessus, on ne change rien en
redonnant le nom p àl ’indice servant àd écrire la
deuxième somme :
S n =
n
p=1
1
p
−
n+1
p=2
1
p
Tous les termes d’indice p compris entre 2et n s’éliminent ;ilreste :
S n = 1 −
1
n +1
Avec un peu d’habitude, on pourra effectuer ce changement d’indice sans modifier sonnom ;ondira qu’on
«change p en p +1 ».
Hachette Livre–HPrépa /Math –Laphotocopie non autorisée est un délit
167
COURS
9
Montrons l’unicité :
Supposonsque n = 2
p
(2q +1)=2
p
(2q
+1).
Si p p
, 2
p−p
(2q +1 ) = 2 q
+1 . Le second
membre étanti mpair, le premier doit l’être aussi ;
d’où p = p
. Il reste 2q +1 = 2 q
+1;d ’où
q = q
.
Remarque :Onvient de mettre en évidence unebijection
de N
∗
dans N
2
.
1.4 • Suites définies par récurrence
Soit E un ensemble quelconque. On appelle suite d’éléments de E uneapplication de N (ou parfois d’une partie de N)d ans E. L’imagedel’entier n est
noté u n . La suite tout entière est notée (u n )( ne pas oublier les parenthèses).
Une suite peut être définie par son premier terme, parexemple u 0 , et une relation
donnant chaque terme en fonctiond up récédent : u n+1 = f (u n ). Le théorème
de récurrence permet d’affirmer l’existence et l’unicité d’une suite vérifiant ces
conditions ;o nd it que la suite estd éfinie par récurrence, ou que c’est une suite
récurrente.
IMPORTANT
La notation i n’est qu’un intermédiaire permettant de décrire la somme
ou le produit;elle n’apparaît pas dans
le résultat. On dit que c’est une variable muette.
n
i=1
ui et
n
j=1
uj représentent exactement la même chose.
Exemples :
La somme S n =
n
i=1
u i est définiepar S 0 = 0e tpour tout n ∈ N :
S n+1 = S n + u n+1 . Par exemple
n
i=1
i =
n(n +1)
2
.
De même, le produit P n =
n
i=1
u i est défini par P 0 = 1e tpour tout n ∈ N :
P n+1 = P n ×u n+1 . Par exemple : n! =
n
i=1
i.
APPLICATION 3
Changement d’indice dansune somme
Simplifierl’expression :S n =
n
p = 1
1
p
−
1
p+1
.
On peut séparer la somme en deux termes :
S n =
n
p=1
1
p
−
n
p=1
1
p +1
Dans le second terme, effectuons le changement d’indice q = p +1:
S n =
n
p = 1
1
p
−
n +1
q=2
1
q
D’aprèsl ar emarque ci-dessus, on ne change rien en
redonnant le nom p àl ’indice servant àd écrire la
deuxième somme :
S n =
n
p=1
1
p
−
n+1
p=2
1
p
Tous les termes d’indice p compris entre 2et n s’éliminent ;ilreste :
S n = 1 −
1
n +1
Avec un peu d’habitude, on pourra effectuer ce changement d’indice sans modifier sonnom ;ondira qu’on
«change p en p +1 ».
Hachette Livre–HPrépa /Math –Laphotocopie non autorisée est un délit
167