Planche no 2.

Raisonnement par récurrence : corrigé

Exercice no 1
Montrons par récurrence que : ∀n ∈ N, 2n > n.
• Pour n = 0, 20 = 1 > 0. L’inégalité à démontrer est donc vraie quand n = 0.
• Soit n > 0. Supposons que 2n > n et montrons que 2n+1 > n + 1.

2n+1 = 2 × 2n
> 2(n + 1) (par hypothèse de récurrence)
=n+1+n+1
> n + 1.
On a montré par récurrence que :
∀n ∈ N, 2n > n.

Exercice no 2
Montrons par récurrence que : ∀n > 4, n! > n2 .
• Pour n = 4, 4! = 4 × 3 × 2 × 1 = 24 et 42 = 16. Puisque 24 > 16, l’inégalité à démontrer est donc vraie quand n = 4.
• Soit n > 4. Supposons que n! > n2 et montrons que (n + 1)! > (n + 1)2 .

(n + 1)! = (n + 1) × n!
> (n + 1) × n2 (par hypothèse de récurrence).

Or, (n + 1) × n2 − (n + 1)2 = (n + 1)(n2 − n − 1) = (n + 1)(n(n − 1) − 1) > 5 × (4 × 3 − 1) = 55 > 0 et donc

(n + 1) × n2 > (n + 1)2 puis (n + 1)! > (n + 1)2 .
On a montré par récurrence que :

∀n > 4, n! > n2 .

Exercice no 3
Montrons par récurrence que : ∀n > 2, n est divisible par au moins un nombre premier.
• 2 est divisible par 2 qui est un nombre premier. La propriété à démontrer est donc vraie quand n = 2.
• Soit n > 2. Supposons que pour tout k ∈ J2, nK, k est divisible par au moins un nombre premier et montrons que n + 1
est divisible par au moins un nombre premier.
Si n + 1 est un nombre premier, n + 1 admet au moins un diviseur premier à savoir lui-même. Sinon, n + 1 n’est pas
premier. Dans ce cas, il existe deux entiers a et b éléments de J2, nK tels que n + 1 = a × b. Par hypothèse de récurrence,
l’entier a est divisible par au moins un nombre premier p. L’entier p divise l’entier a et l’entier a divise l’entier n + 1.
Donc l’entier p divise l’entier n + 1.
Dans tous les cas, l’entier n + 1 est divisible par au moins un nombre premier.
On a montré par récurrence que tout entier supérieur ou égal à 2 est divisible par au moins un nombre premier.
Exercice no 4
Montrons par récurrence que : ∀n ∈ N, un = (−2)n + 3n .
• (−2)0 + 30 = 2 = u0 et (−2)1 + 31 = 1 = u1 . L’égalité à démontrer est donc vraie quand n = 0 et n = 1.
• Soit n > 0. Supposons que un = (−2)n + 3n et que un+1 = (−2)n+1 + 3n+1 et montrons que un+2 = (−2)n+2 + 3n+2 .

un+2 = un+1 + 6un

= (−2)n+1 + 3n+1 + 6 ((−2)n + 3n ) (par hypothèse de récurrence)

= (−2 + 6) × (−2)n+2 + (3 + 6) × 3n = 4 × (−2)n+2 + 9 × 3n

= (−2)2 × (−2)n+2 + 32 × 3n = (−2)n+2 + 3n+2 .
On a montré par récurrence que :

http ://www.maths-france.fr 1 c Jean-Louis Rouget, 2014. Tous droits réservés.

 ∀n ∈ N, (−2)n + 3n .

Exercice no 5
n
X n(n + 1)
1) Montrons par récurrence que : ∀n > 1, k= .
2
k=1
1
X 1 × (1 + 1)
• Pour n = 1, k=1= .
2
k=1
n n+1
X n(n + 1) X (n + 1)(n + 2)
• Soit n > 1. Supposons que k= et montrons que k= .
2 2
k=1 k=1

n+1 n
X X n(n + 1)
k= k + (n + 1) = + (n + 1) (par hypothèse de récurrence)
2
k=1 k=1
n  (n + 1)(n + 2)
= (n + 1) +1 = .
2 2
On a montré par récurrence que :
n
X n(n + 1)
∀n > 1, k= .
2
k=1

On peut donner plusieurs démonstrations directes.

n
X n
X n
X
1ère demonstration. Pour k > 1, (k + 1)2 − k2 = 2k + 1 et donc (k + 1)2 − k2 = 2


k+ 1 ce qui s’écrit
k=1 k=1 k=1
n n n
2
X X
2
X n(n + 1)
(n + 1) − 1 = 2 k + n ou encore 2 k = n + n ou enfin k= .
2
k=1 k=1 k=1

2ème demonstration. On écrit

1 + 2 + 3 + ... + (n − 1) + n = S
n + (n − 1) + (n − 2) + ... + 2 + 1 = S
et en additionnant (verticalement), on obtient 2S = (n + 1) + (n + 1) + . . . + (n + 1) = n(n + 1) d’où le résultat. La même
| {z }
n termes
démonstration s’écrit avec le symbole sigma :
n
X n
X n
X n
X
2S = k+ (n + 1 − k) = (k + n + 1 − k) = (n + 1) = n(n + 1).
k=1 k=1 k=1 k=1

3ème demonstration. On compte le nombre de points d’un rectangle ayant n points de large et n + 1 points de long.
Il y en a n(n + 1). Ce rectangle se décompose en deux triangles isocèles contenant chacun 1 + 2 + ... + n points. D’où le
résultat.

∗ ∗ ∗ ... ... ∗
.. ..
∗ ∗ . .
∗ ∗ ∗
.. .. .. ..
. . . .
∗ ∗ ∗
.. ..
. . ∗ ∗
∗ ... ... ∗ ∗ ∗
   
n n
4ème démonstration. Dans le triangle de Pascal, on sait que pour n et p entiers naturels donnés, + =
  p p+1
n+1
. Donc, pour n > 2 (le résultat est clair pour n = 1),
p+1

http ://www.maths-france.fr 2 c Jean-Louis Rouget, 2014. Tous droits réservés.

 n n
X X n(n + 1)
1 + 2 + ... + n = 1 + C1k = 1 + (C2k+1 − C2k ) = 1 + (C2n+1 − 1) = .
2
k=2 k=2
2) Pour k > 1, (k + 1)3 − k3 = 3k2 + 3k + 1. Donc, pour n > 1 :
n
X n
X n
X n
X
k2 + 3 (k + 1)3 − k3 = (n + 1)3 − 1.


3 k+ 1=
k=1 k=1 k=1 k=1
D’où,

n  
X
2 1 3 n(n + 1) 1 1
k = (n + 1) − 1 − 3 − n = (2(n + 1)3 − 3n(n + 1) − 2(n + 1)) = (n + 1)(2n2 + n),
3 2 6 6
k=1
et donc
n
X n(n + 1)(2n + 1)
∀n > 1, k2 = .
6
k=1

Pour k ≥ 1, (k + 1)4 − k4 = 4k3 + 6k2 + 4k + 1. Donc, pour n ≥ 1, on a

n
X n
X n
X n
X n
X
k3 + 6 k2 + 4 (k + 1)4 − k4 = (n + 1)4 − 1.


4 k+ 1=
k=1 k=1 k=1 k=1 k=1
D’où :

n
X 1
1
k3 = (n + 1)4 − 1 − n(n + 1)(2n + 1) − 2n(n + 1) − n = ((n + 1)4 − (n + 1)(n(2n + 1) + 2n + 1)
4 4
k=1
2 2


1 4 2

(n + 1) (n + 1) − (2n + 1) n2 (n + 1)2
= (n + 1) − (n + 1) (2n + 1) = =
4 4 4
n n
! 2
X n2 (n + 1)2 X
∀n > 1, k3 = = k .
4
k=1 k=1

Pour k > 1, (k + 1)5 − k5 = 5k4 + 10k3 + 10k2 + 5k + 1. Donc, pour n > 1,

n
X n
X n
X n
X n
X n
X
5 k4 + 10 k3 + 10 k2 + 5 k+ 1= ((k + 1)5 − k5 ) = (n + 1)5 − 1.
k=1 k=1 k=1 k=1 k=1 k=1
D’où :

n  
X
4 1 5 5 2 2 5 5
k = (n + 1) − 1 − n (n + 1) − n(n + 1)(2n + 1) − n(n + 1) − n
5 2 3 2
k=1
1
= (6(n + 1)5 − 15n2 (n + 1)2 − 10n(n + 1)(2n + 1) − 15n(n + 1) − 6(n + 1))
30
1 n(n + 1)(6n3 + 9n2 + n − 1)
= (n + 1)(6n4 + 9n3 + n2 − n) =
30 30
Finalement,
n
X n(n + 1)
∀n ∈ N∗ , k=
2
k=1
n
X n(n + 1)(2n + 1)
∀n ∈ N∗ , k2 =
6
k=1
n n
!2
∗
X
3 n2 (n + 1)2 X
∀n ∈ N , k = = k
4
k=1 k=1
n
X n(n + 1)(6n3 + 9n + n − 1)2
∀n ∈ N , ∗
k4 = .
30
k=1

http ://www.maths-france.fr 3 c Jean-Louis Rouget, 2014. Tous droits réservés.

Exercice no 6
n
X 1 n
1) Montrons par récurrence que ∀n > 1, = .
k(k + 1) n+1
k=1
1
X 1 1 1
• Pour n = 1, = = et la formule proposée est vraie pour n = 1.
k(k + 1) 2 1+1
k=1
n n+1
X 1 n X 1 n+1
• Soit n > 1. Supposons que = et montrons que = .
k(k + 1) n+1 k(k + 1) n+2
k=1 k=1

n+1 n
!
X 1 X 1 1
= +
k(k + 1) k(k + 1) (n + 1)(n + 2)
k=1 k=1
n 1
= + (par hypothèse de récurrence)
n + 1 (n + 1)(n + 2)
n(n + 2) + 1 n2 + 2n + 1
= =
(n + 1)(n + 2) (n + 1)(n + 2)
(n + 1)2 n+1
= =
(n + 1)(n + 2) n+2

On a montré par récurrence que :

n
X 1 n
∀n > 1, = .
k(k + 1) n+1
k=1

Démonstration directe. Pour k > 1,

1 (k + 1) − k 1 1
= = − ,
k(k + 1) k(k + 1) k (k + 1)
et donc,

n n n n n+1
X 1 X 1 X 1 X 1 X1
= − = −
k(k + 1) k (k + 1) k k
k=1 k=1 k=1 k=1 k=2
1 n
=1− = .
n+1 n+1
n
X 1 n(n + 3)
2) Montrons par récurrence que ∀n > 1, = .
k(k + 1)(k + 2) 4(n + 1)(n + 2)
k=1
1
X 1 1 1 × (1 + 3)
• Pour n = 1, = = et la formule proposée est vraie pour n = 1.
k(k + 1)(k + 2) 6 4 × (1 + 1)(1 + 2)
k=1
n n+1
X 1 n(n + 3) X 1 (n + 1)(n + 4)
• Soit n > 1. Supposons que = et montrons que = .
k(k + 1)(k + 2) 4(n + 1)(n + 2) k(k + 1)(k + 2) 4(n + 2)(n + 3)
k=1 k=1

n+1 n
!
X 1 X 1 1
= +
k(k + 1)(k + 2) k(k + 1)(k + 2) (n + 1)(n + 2)(n + 3)
k=1 k=1
n(n + 3) 1
= + (par hypothèse de récurrence)
4(n + 1)(n + 2) (n + 1)(n + 2)(n + 3)
n(n + 3)2 + 4 n3 + 6n2 + 9n + 4
= =
4(n + 1)(n + 2)(n + 3) 4(n + 1)(n + 2)(n + 3)
2
(n + 1)(n + 5n + 4) (n + 1)(n + 4)
= =
4(n + 1)(n + 2)(n + 3) 4(n + 2)(n + 3)

On a montré par récurrence que :

http ://www.maths-france.fr 4 c Jean-Louis Rouget, 2014. Tous droits réservés.

 n
X 1 n(n + 3)
∀n > 1, = .
k(k + 1)(k + 2) 4(n + 1)(n + 2)
k=1

Démonstration directe. Pour k > 1,

 
1 1 (k + 2) − k 1 1 1
= = − ,
k(k + 1)(k + 2) 2 k(k + 1)(k + 2) 2 k(k + 1) (k + 1)(k + 2)
et donc,

n n n
! n n+1
!
X 1 1 X 1 X 1 1 X 1 X 1
= − = −
k(k + 1)(k + 2) 2 k(k + 1) (k + 1)(k + 2) 2 k(k + 1) k(k + 1)
k=1 k=1 k=1 k=1 k=2
n2 + 3n
 
1 1 1 n(n + 3)
= − = = .
2 2 (n + 1)(n + 2) 4(n + 1)(n + 2) 4(n + 1)(n + 2)

Exercice no 7
pn
Montrons par récurrence que, pour n > 2, Hn peut s’écrire sous la forme où qn est un entier pair et pn est un entier
qn
impair (la fraction précédente n’étant pas nécessairement irréductible mais à coup sûr pas un entier).
3
• Pour n = 2, H2 = et H2 est bien du type annoncé.
2
pk
• Soit n > 2. Supposons que pour tout entier k tel que 2 6 k 6 n, on ait Hk = où pk est un entier impair et qk est
qk
pn+1
un entier pair et montrons que Hn+1 = où pn+1 est un entier impair et qn+1 est un entier pair.
qn+1
pn 1 (n + 1)pn + qn
(Recherche. L’idée Hn+1 = + = ne marche à coup sur que si (n + 1)pn + qn est impair ce qui
qn n + 1 (n + 1)qn
est assuré si n + 1 est impair et donc si n est pair).
pn 1 (2k + 1)pn + qn
1er cas. Si n est pair, on peut poser n = 2k où k ∈ N∗ . Dans ce cas, Hn+1 = + = . (2k + 1)
qn 2k + 1 (2k + 1)qn
est pn sont impairs et donc (2k + 1)pn est impair puis (2k + 1)pn + qn est impair car qn est pair. D’autre part, qn est
pair et donc (2k + 1)qn est pair. Hn+1 est bien le quotient d’un entier impair par un entier pair.
2ème cas. Si n est impair, on pose n = 2k − 1 où k > 2 (de sorte que 2k − 1 > 3).

2k k k−1
X 1 X 1 X 1
Hn+1 = = +
i 2i 2i + 1
i=1 i=1 i=0
(en séparant les fractions de dénominateurs pairs des fractions de dénominateurs impairs)
k k−1 k−1
1X1 X 1 1 X 1
= + = Hk + .
2 i 2i + 1 2 2i + 1
i=1 i=0 i=0

Maintenant, en réduisant au même dénominateur et puisque un produit de nombres impairs est impair, on voit que
k−1
X 1 K
est du type où K et K ′ sont des entiers. Ensuite, puisque 2 6 k 6 2k − 1 = n, par hypothèse de
2i + 1 2K ′ + 1
i=0
pk
récurrence, Hk = où pk est un entier impair et qk un entier pair. Après réduction au même dénominateur, on obtient
qk
pk K (2K ′ + 1)pk + 2Kqk
Hn+1 = + = .
2qk 2K + 1
′ 2qk (2K ′ + 1)
2Kqk est un entier pair et (2K ′ + 1)pk est un entier impair en tant que produit de deux nombres impairs. Donc le
numérateur est bien un entier impair et puisque 2qk(2K ′ + 1) est un entier pair, Hn+1 est encore une fois de la forme
désirée.
On a montré par récurrence que pour tout naturel n > 2, Hn est le quotient d’un entier impair par un entier pair et en
particulier n’est pas un entier.

http ://www.maths-france.fr 5 c Jean-Louis Rouget, 2014. Tous droits réservés.