Lycée Louis-Le-Grand, Paris Pour le 12/09/2023

MP2I – Mathématiques
A. Troesch

DM no 1 : Révisions, récurrences

Corrigé du problème 1 – (D’après un vieux sujet de Bac des années 80)

Partie I –
L’objet de cette partie est d’étudier la fonction f définie sur l’intervalle r0, `8r par :
lnp1 ` xq
f pxq “ si x ‰ 0 et f p0q “ 1.
x
1. Encadrement de lnp1 ` xq.
1
(a) ‚ Pour tout t ě 0, 1 ` t ě 1, donc ď 1.
1`t
1
‚ Pour tout t ě 0, l’inégalité 1 ´ t ď équivaut à p1 ´ tqp1 ` tq ď 1, c’est-à-dire à 1 ´ t2 ď 1, donc à
1`t
1
t2 ě 0, qui est vérifiée. Ainsi, 1 ´ t ď .
1`t
1
Des deux inégalités on déduit l’encadrement 1 ´ t ď ď 1.
1`t
(b) Soit x ě 0. On intègre l’encadrement précédent entre 0 et x (l’encadrement étant vrai sur tout l’intervalle
r0, xs) :
żx żx ż1
dt
p1 ´ tq dt ď ď 1 dt,
0 0 1`t 0
c’est-à-dire :
x2
x´ ď lnp1 ` xq ď x.
2
Ces inégalités peuvent aussi s’obtenir par étude de fonction. On peut aussi remarquer que l’inégalité de
droite affirme que la courbe de x ÞÑ lnp1 ` xq reste en dessous de sa tangente en 0 (au moins sur l’axe réel
positif), ce qui est conséquence de la concavité du logarithme. Vous verrez plus tard que la concavité est
caractérisée par la négativité de la dérivée seconde, ce qui fournit une autre démontration, très rapide, de
l’inégalité lnp1 ` xq ď x.
2. Étude d’une fonction auxiliaire.
Soit g la fonction définie sur r0, `8r par
2x
gpxq “ lnp1 ` xq ´ .
2`x
(a) La fonction g est dérivable sur r0, `8r comme somme de deux fonctions dérivables, celle de droite en tant
que quotient de deux fonctions dérivables, le dénominateur ne s’annulant pas sur l’intervalle considéré, celle
de gauche en tant que composée de deux fonctions dérivables, l’une (x ÞÑ 1 ` x) sur r0, `8r, et à valeurs
dans r1, `8r, intervalle sur lequel l’autre (y ÞÑ lnpyq) est dérivable.
Pour tout x P r0, `8r, on a alors

1 2p2 ` xq ´ 2x p2 ` xq2 ´ 4p1 ` xq x2

g 1 pxq “ ´ “ “ ě0
1`x p2 ` xq2 p1 ` xqp2 ` xq2 p1 ` xqp2 ` xq2

D’un autre côté, pour x ě 0, 1 ` x ě 1 et 2 ` x ě 2, donc

x2 x2
2
ď .
p1 ` xqp2 ` xq 4
On a bien obtenu l’encadrement recherché :

x2
@x ě 0, 0 ď g 1 pxq ď .
4

1
 L’étude de la dérivabilité de g a ici été faite de façon très détaillée, un peu trop. À terme, on éludera un
peu cette étude. Mais il est important de savoir qu’on sait faire (notamment la justification correcte pour
les composées, en faisant attention aux intervalles sur lesquels considérer la dérivabilité de chacune des
fonctions).
(b) On trouve un encadrement de g en intégrant l’encadrement entre 0 et x, pour x ě 0 :

x3 x3
0 ď gpxq ´ gp0q ď , donc: 0 ď gpxq ď .
12 12

3. La fonction f est dérivable sur s0, `8r, de dérivée donnée par :

x
´ lnp1 ` xq
@x Ps0, `8r, f 1 pxq “ 1`x
.
x2
Pour tout x ą 0, le signe de g 1 pxq est donc le même que celui de

x x 2x x2
hpxq “ ´ lnp1 ` xq “ ´gpxq ` ´ “ ´gpxq ´ ď 0,
1`x 1`x 2`x p1 ` xqp2 ` xq

puisque g est positive sur s0, `8r, ainsi que le terme de droite.
Ainsi, f est décroissante sur s0, `8r, donc sur r0, `8r , par continuité de f en 0.
4. Étude de f aux bornes de l’intervalle de définition.
(a) Pour tout x ą 0
x ` 1 lnp1 ` xq
f pxq “ ¨ .
x 1`x
x`1 lnp1 ` xq
Or, lim “ 1 et par croissances comparées, puisque 1 ` x Ñ `8. Ainsi,
xÑ`8 x 1`x

lim f pxq “ 0.
xÑ`8

Il peut être intéressant de noter qu’il n’y a pas une façon unique de parvenir à cette limite : on peut aussi
mener le calcul de la sorte pour se ramener aux croissances comparées :

lnpxq ln 1 ` x1
` ˘
f pxq “ ` ,
x x
ces deux termes tendant vers 0, le premier par croissances comparées, le second n’étant pas une forme
indéterminée.
(b) Il est naturel d’essayer dans un premier temps d’utiliser l’encadrement obtenu dans la question 1b : pour
tout x ą 0,
x2 x ´ lnp1 ` xq 1
´ ď lnp1 ` xq ´ x ď 0 donc: 0ď ď .
2 x2 2
On se rend compte que l’encadrement n’est pas assez fin pour conclure. On remarque que l’encadrement de
g obtenu dans la question 2b permet aussi d’obtenir un encadrement de lnp1 ` xq, et a une précision plus
importante lorsque x est proche de 0 (d’ordre 3 au lieu de 2). On a donc :

2x x2 x3
0 ď lnp1 ` xq ´ “ lnp1 ` xq ´ x ` ď .
2`x 2`x 12
On en déduit que pour tout x ą 0,
1 x x ´ lnp1 ` xq 1
´ ď ď .
2 ` x 12 x2 2`x
Lorsqu’on fait tendre x vers 0` , les deux termes encadrant admettent la limite 1
2. On en déduit, par le
théorème d’encadrement, que
x ´ lnp1 ` xq 1
lim 2
“ .
xÑ0 ` x 2
Cela ne répond qu’à moitié à la question posée, puisqu’il faut aussi étudier la limite à gauche. Cette limite
peut s’obtenir de même. Le raisonnement global peut facilement s’adapter, il y a juste à changer le sens de
certaines inégalités (notamment du fait qu’on intègre avec des bornes données en sens décroissant).

2
 On peut aussi (mais cela nécessite un peu d’habitude technique) se ramener au cas positif en se rappelant
que pour tout x Ps ´ 1, 0s,
ˆ ˙ ˆ ˙
1 x
lnp1 ` xq “ ´ ln “ ´ ln 1 ´ .
1`x 1`x
x
En posant y “ ´ , on a alors y ě 0, et y Ñ 0` lorsque x Ñ 0´ . On peut alors appliquer le résultat
1`x
précédent sur y :
´x
1 y ´ lnp1 ` yq 1`x ` lnp1 ` xq lnp1 ` xq ´ x lnp1 ` xq
“ lim “ lim ¯2 “ lim ` .
2 yÑ0` y2 p1 ` xqx2 xp1 ` xq
´
xÑ0´ x xÑO´
1`x

lnp1 ` xq
Or, lim “ 1, donc
xÑ0´ x
lnp1 ` xq lnp1 ` xq ´ x 1
lim “1 donc: lim “´ .
xÑ0´ xp1 ` xq xÑ0´ p1 ` xqx2 2

x ´ lnp1 ` xq 1
En rétablissant le signe et en multipliant par x ` 1 de limite 1, on a bien lim´
2
“ ..
xÑ0 x 2
L’égalité de la limite à gauche et de la limite à droite amènent l’existence de la limite et :

x ´ lnp1 ` xq 1
lim 2
“
xÑ0 x 2

Le résultat qu’on vient de démontrer est en fait l’expression du développement limité à l’ordre 2 de lnp1 ` xq
au voisinage de 0. Vous pouvez vérifier qu’on peut en effet reexprimer ce qu’on vient de démontrer sous la
forme suivant :
x2
lnp1 ` xq “ x ´ ` o px2 q,
2 xÑ0

où opx q désigne un terme négligeable devant x (c’est-à-dire infiniment plus petit que x2 ) au voisinage de
2 2

0.
(c) Cela dit, l’étude de la dérivabilité de f ne nécessite que le calcul de la limite à droite de l’expression
précédente, puisque f n’est pas définie à gauche de 0. C’est peut-être une erreur d’énoncé, mais qui au
passage nous a permis de voir comment exploiter la symétrie du logarithme pour déduire quelque chose sur
l’intervalle s0, 1s à partir de quelque chose sur l’intervalle r1, `8r.
Pour étudier la dérivabilité de f , on exprime le taux d’accroissement à droite : pour tout x ą 0,
lnp1`xq
f pxq ´ f p0q 2 ´1 lnp1 ` xq ´ x 1
“ “ ÝÑ ´ .
x x x2 xÑ0` 2

1
Ainsi, f est dérivable en 0 et f 1 p0q “ ´ .
2
x
Connaissant f p0q “ 1, on a alors aisément une équation de la tangente en 0 : y “ 1 ´ .
2
(d) Ci-dessous la courbe de f , avec sa tangente en 0 :

1
|

| | |
|

1
|

Partie II –
L’objet de cette partie est d’étudier la suite pun qnPN de nombres réels définies par les relations :

U0 “ c et un`1 “ lnp1 ` un q si n ě 0,

où c est un nombre réel strictement positif donné.

3
 1. Avant d’étudier la convergence, remarquons que pun q est bien définie, c’est-à-dire que un existe pour tout n P N.
cela provient du fait que s0, `8r est un intervalle stable par x ÞÑ lnp1 ` xq (c’est-à-dire que pour tout x Ps0, 8r,
on a aussi lnp1 ` xq Ps0, `8r). On en déduit en effet par une récurrence immédiate que pour tout n P N, un
existe et vérifie un ą 0.
L’inégalité qu’on vient d’établir nous permet d’utiliser l’encadrement de la question I-1b (ou juste la majora-
tion) : pour tout n P N,
lnp1 ` un q ď un donc: un`1 ď un .

Ainsi, pun qnPN est décroissante et minorée par 0, donc pun qnPN converge vers une certaine limite réelle ℓ P R` .
On passe alors à la limite lorsque n tend vers `8 dans la relation un`1 “ lnp1 ` un q. Comme ln est continue,
cela nous donne une relation sur ℓ :
ℓ “ lnp1 ` ℓq.
Cette équation admet une solution évidente dans R` qui est ℓ “ 0. Montrons que c’est la seule.
Pour cela, on peut étudier les variations de la fonction x ÞÑ x ´ lnp1 ` xq, ou alors, remarquer que ℓ est solution
non nulle de l’équation étudiée si et seulement si f pℓq “ 1, ce qui est impossible pour ℓ ą 0 d’après les variations
de f .
Ainsi, ℓ “ 0 .
On pose désormais c “ 1. Le but de la fin du problème est de déterminer la limite de pnun q. Pour tout n ě 0, on pose
vn “ u1n .
2. Pour commencer, remarquons que pvn q est bien définie, puisqu’on a montré que pour tout n P N, un ą 0. Pour
tout n P N, on a alors :

1 1 1 1 un ´ lnp1 ` un q un
vn`1 ´ vn “ ´ “ ´ “ 2
¨ .
un`1 un lnp1 ` un q un un lnp1 ` un q

D’après l’expression des limites remarquables et la question I-4b (utilisable du fait que un Ñ 0), on a

1
lim vn`1 ´ vn “ .
2

3. Pour commencer, remarquons que pour tout x Ps0, 1s,

1 1 1 x lnp1 ` xq ´ 2x ` 2 lnp1 ` xq px ` 2q lnp1 ` xq ´ 2x px ` 2qgpxq

´ ` “ “ “ ,
2 lnp1 ` xq x 2x lnp1 ` xq 2x lnp1 ` xq 2x lnp1 ` xq

et là, on comprend mieux pourquoi on a introduit cette fonction g. Elle apparaît naturellement dans les calculs
effectués.
Il reste donc à montrer que pour tout x Ps0, 1s,

px ` 2qgpxq 3x
0ď ď .
2x lnp1 ` xq 16
L’inégalité de gauche résulte de la positivité de g, prouvée en I-2b. De plus, la majoration obtenue à cette même
question montre que
px ` 2qgpxq x2 px ` 2q
ď .
2x lnp1 ` xq 24 lnp1 ` xq
Par ailleurs, toujours le même encadrement nous permet de minorer le logarithme :
2x
lnp1 ` xq ě ,
x`2
d’où
px ` 2qgpxq xpx ` 2q2 9x 3x
ď ď “ ,
2x lnp1 ` xq 48 48 16
en majorant 2 ` x par 3 sur s0, 1s. Ainsi, on a bien obtenu l’encadrement voulu :

1 3x 1 1 1
´ ď ´ ď .
2 16 lnp1 ` xq x 2

4
4. En particulier, la suite pun q étant strictement décroissante de limite nulle, et initialisée par u0 “ 1, pour tout
n ě 0, un Ps0, 1s, et on peut donc utiliser la question précédente avec x “ un :
1 3un 1 1 1
´ ď ´ ď .
2 16 lnp1 ` un q un 2
1 1
Or, “ “ vn`1 d’où l’encadrement
lnp1 ` un q un`1

1 3un 1
´ ď vn`1 ´ vn ď . (1)
2 16 2
3un
Puisque 16 ď 14 , il vient :
1 1
ď vn`1 ´ vn ď ,
4 2
et en sommant ces inégalités et par téléscopage, on obtient pour tout n ě 0 :
n´1
n ÿ 1 n
ď vk`1 ´ vk “ vn ´ v0 “ ´1ď .
4 k“0
u n 2

On en déduit, pour tout n ě 0 :

n`4 1 n`2 2 4
ď ď donc: ď un ď .
4 un 2 n`1 n`4

5. On fait cette fois la somme des encadrements (1) :

n´1
n 3 ÿ 1 n
´ uk ď ´1ď .
2 16 k“0 un 2

En divisant par n, il vient :

n´1
1 3 ÿ 1 1 1
´ uk ď ´ ď .
2 16n k“0 nun n 2
n´1
1 ÿ
Montrons que uk “ 0. Vous verrez plus tard que ceci est une conséquence immédiate du théorème de
n k“0
Cesaro assurant que la limite des moyennes successives des termes d’une suite est égale à la limite de la
suite, si celle-ci existe. On peut aussi prouver ce résultat en se servant du fait que la somme partielle de la
ÿ1
série harmonique alternée est de l’ordre de lnpnq, en utilisant l’encadrement obtenu pour un . On peut
n
cependant s’en sortir par une étude plus élémentaire ne nécessitant pas de connaître ces deux résultats. Posons,
pour tout n P N˚ ,
n n
ÿ 1 1 ÿ 1 Sn
Sn “ et wn “ “ .
k“1
k n k“1
k n
On a alors :
ˆ ˙
Sn Sn`1 1 1 1 1 1 Sn`1 Sn`1 ´ 1
wn ´ wn`1 “ ´ “ pSn ´ Sn`1 q ` Sn`1 ´ “´ ` “ ě 0.
n n`1 n n n`1 n n ` 1 npn ` 1q npn ` 1q
Ainsi, pwn q est décroissante, et minorée par 0, donc converge vers un réel ℓ.
Adaptons l’argument de condensation de Cauchy qu’on avait utilisé pour démontrer la divergence de la série
harmonique. On remarque que 2w2n et wn se simplifient bien :
2n
1 ÿ 1 1 ÿ 1 1
2w2n ´ wn “ 2n ď ď ,
n k“n`1 k n k“n`1 n n

la positivité de cette expression étant évidente par la première égalité. Le théorème d’encadrement amène alors

2w2n ´ wn Ñ 0 soit: 2ℓ ´ ℓ “ 0 soit: ℓ “ 0.

Par ailleurs, en encadrant sommant l’encadrement de pun q obtenu dans la question précédente,
n´1 n´1 n´1
2 ÿ 1 1 ÿ 4 ÿ 1
uk ď ,
n k“0 k ` 2 n k“0 n k“0 k ` 4

5
 c’est-à-dire
n´1
1 2pn ` 1q 1 ÿ 11 4pn ` 3q
pwn`1 ´ qˆ ď uk ď pwn`3 ´ q .
n`1 n n k“0 6pn ` 3q n
Les deux encadrant ayant une limite nulle, il vient :
n´1
1 ÿ
lim uk “ 0,
n k“0

d’où finalement, par encadrement

ˆ ˙
1 1 1
lim ´ “ , donc: lim nun “ 2 .
nun n 2

Corrigé du problème 2 – Le problème de Josèphe (ou Josephus)

Partie I – Traitement informatique

1. (a) On crée une liste des entiers de 1 à n, et on élimine successivement les personnes à partir de la personne
numérotée k (donc en indice k ´ 1) et en progressant de k en k. On remarquera que le fait d’enlever de
la liste les personnes éliminées décale toutes les indexations suivantes, et il ne faut donc progresser que de
k ´ 1 dans les indices à chaque étape. Par ailleurs, lorsque les indices dépassent la longueur de la liste, il faut
revenir au début de la liste, ce qu’on fait en réduisant modulo la longueur de la liste. On s’arrête lorsqu’il
ne reste plus qu’une personne dans la liste.
def survivant(n,k):
groupe = [i+1 for i in range(n)]
victime = k-1
while len(groupe) > 1:
del groupe[victime]
victime = (victime + k-1) % len(groupe)
# Attention la suppression du precedent cree un decalage, on
# n’avance donc que de k-1 dans les indices
return groupe[0]

Pour les applications numériques :

print(survivant(41,3))
print(survivant(41,2))

On trouve respectivement 31 et 19.

L’algorithme ainsi conçu est loin d’être optimisé. En effet, la suppression d’un élément dans une liste Python
se faisant en temps linéaire (dans le pire des cas), puisqu’il faut décaler tous les termes suivants, on obtient
un algorithme quadratique (dont le temps d’exécution croît comme n2 , lorsque n est la taille de la donnée
initiale).
On peut améliorer cela en ne supprimant pas les termes de la liste, mais en les marquant d’une façon ou d’une
autre. Lors de l’élimination, on parcourt alors la liste circulairement dans l’ordre, en comptant les personnes
non encore marquées pour savoir où on s’arrête. La complexité obtenue est meilleure, mais les différentes
étapes ne sont pas en temps constant, puisque plus on a éliminé de personnes, plus le parcours à faire pour
éliminer la personne suivante est long. Il n’est pas dur de se convaincre qu’on obtient ainsi un algorithme
en n lnpnq. On peut enfin aboutir à une complexité linéaire en faisant effectivement les suppressions, mais
en utilisant des listes chaînées au lieu des listes Python.
2. Il suffit de s’arrêter dès qu’il ne reste que p personnes dans la liste. On renvoie cette fois la liste entière.
def survivants(n,k,p):
groupe = [i+1 for i in range(n)]
victime = k-1
while len(groupe) > p:
del groupe[victime]
victime = (victime + k-1) % len(groupe)
return groupe

6
 Pour les applications numériques :
print(survivants(41,3,2))
print(survivants(100,7,50))

On obtient respectivement [16, 31] et

[1, 2, 4, 6, 8, 11, 15, 16, 17, 18, 20, 25, 26, 27, 29, 33, 34, 37, 39, 40, 44, 45, 47, 50,
52, 55, 57, 58, 59, 61, 64, 66, 67, 68, 72, 73, 74, 76, 78, 81, 82, 83, 85, 88, 90, 92, 93, 94,
96, 100]

Partie II – Décomposition en base 2

1. Soit n P N˚ et pc0 , . . . , ck q une décomposition de n en base 2. Alors :

k
ÿ
n“ ci 2 i
i“0
k
ÿ
“ c0 ` ci 2 i
i“1
k
ÿ
“ c0 ` 2 ci 2i´1
i“1
k´1
ÿ
“ c0 ` 2 ci`1 2i .
i“0

k´1
ÿ
En posant r “ c0 P t0, 1u et q “ ci`1 2i P N, on reconnaît la forme d’une division euclidienne. Par unicité
i“0
de la division euclidienne, c0 est le reste de la division euclidienne , et l’expression obtenue pour le quotient q
nous assure que pc1 , . . . , ck q en est une décomposition en base 2 .
2. On raisonne par récurrence forte. Pour tout n P N˚ , on note Ppnq la propriété : n admet une unique décompo-
sition en base 2.
2
‚ Initialisation : D’une part 1 “ 1 . D’autre part, pour tout i ą 0, 2i ą 1, donc 1 ne peut pas avoir de chiffre
d’indice i ą 0 dans une de ses décompositions. Ainsi, p1q est l’unique décomposition de 1 en base 2.
‚ Hérédité : soit n ą 1. On suppose que pour tout k P v1, n ´ 1w, k admet une unique décompoisition en base
2.
˚ Soit n “ 2q ` c0 , avec c0 P t0, 1u, la division euclidienne de n par 2. L’entier q vérifie alors 1 ď q ă n.
On peut donc lui appliquer l’hypothèse de récurrence, et en déduire l’existence d’une décomposition
ℓ
ÿ
q“ di 2i ,
i“0

où, pour tout i P v0, ℓw, di P t0, 1u, et dℓ ‰ 0. On obtient alors :

ℓ
ÿ ℓ
ÿ ℓ`1
ÿ
n “ c0 ` 2 di 2i “ c0 ` di 2i`1 “ c0 ` di´1 2i .
i“0 i“0 i“1

En posant k “ ℓ ` 1, et pour tout i P v1, kw, ci “ di´1 , pc0 , . . . , ck q est une décomposition en base 2 de n.
Par conséquent, n admet une décomposition en base 2.
˚ Soit pc0 , . . . , ck q et pd0 , . . . , dℓ q deux décompositions en base 2 de n. D’après la question précédente,
c0 et d0 sont tous deux égaux au reste de la division de n par 2, donc c0 “ d0 (par unicité de la
division euclidienne). De même, pc1 , . . . , ck q et pd1 , . . . , dℓ q sont tous deux des décompositions en base 2
du quotient q P v1, n ´ 1w. Par hypothèse de récurrence, ce quotient admet une unique décomposition,
donc
pc1 , . . . , ck q “ pd1 , . . . , dℓ q, puis: pc0 , . . . , ck q “ pd0 , . . . , dℓ q.
Cela prouve l’unicité de la décomposition de n en base 2.
‚ D’après le principe de récurrence forte, on en conclut que tout n P N˚ admet une unique décomposition en base 2 .

Partie III – Une relation de récurrence pour le cas k “ 2

7
1. Lors du premier tour du groupe, on élimine les personnes de 2 en 2 en partant de la deuxième personne. Ainsi,
on élimine dans un premier temps toutes les personnes paires. Ainsi, à l’issue du procédé, il ne reste pas de
personne paire, donc le dernier survivant Jpnq sera nécessairement impair . Pour n “ 1, le dernier survivant
est aussi la seule personne initialement présente, donc Jp1q “ 1 .
2. Soit n P N˚ . On considère un groupe de 2n personnes. À l’issue du premier tour de table, on a éliminé toutes
les personnes paires, dans l’ordre. La dernière personne éliminée est la personne 2n. Il reste alors les personnes
1, 3, 5, . . . , 2n ´ 1, donc 2ℓ ´ 1, pour ℓ P v1, nw. La personne suivante éliminée étant la personne 3 (correspondant
à ℓ “ 2), tout se passe alors comme si on recommençait l’expérience avec un groupe de n personnes numérotées
cette fois à l’aide de ℓ P v1, nw. On note que la personne numérotée ℓ dans cette nouvelle numérotation est la
personne initialement numérotée 2ℓ ´ 1. Pour cette nouvelle numérotation, on sait par définition que le dernier
survivant est numéroté Jpnq, ce qui correspond à la personne initialement numérotée 2Jpnq ´ 1. On en déduit
donc la relation de récurrence :
@n P N˚ , Jp2nq “ 2Jpnq ´ 1.
On raisonne de même pour un groupe de 2n ` 1 personnes. De la même façon, on commence par éliminer les
personnes paires, puis la personne 1. Il reste cette fois les impaires, de 3 à 2n ` 1, et la personne suivante
éliminée est la personne 5. On renumérote les survivants par 2ℓ ` 1, pour ℓ P v1, nw. Le survivant ultime sera
alors la personne Jpnq dans cette nouvelle numérotation, donc 2Jpnq ` 1 dans l’ancienne numérotation. On en
déduit que
@n P N˚ , Jp2n ` 1q “ 2Jpnq ` 1 .

3. ‚ Soit uα “ Jp2α ´ 1q. On remarque que

uα`1 “ Jp2α`1 ´ 1q “ Jp2p2α ´ 1q ` 1q “ 2Jp2α ´ 1q ` 1 “ 2uα ` 1.
De plus u1 “ Jp1q “ 1. C’est un type de suites s’explicitant facilement (suite arithémtico-géométrique). Soit
vous connaissez la méthode pour le faire (trouver une constante c telle que puα ´ cq soit géométrique), soit,
en attendant de voir cette méthode en cours, on essaye de deviner le résultat à l’aide des premières valeurs :
u2 “ 3, u3 “ 7, u4 “ 15...
On va donc montrer par récurrence sur α P N˚ que uα “ 2α ´ 1.
˚ L’initialisation provient de la valeur de u1 .
˚ Soit α P N˚ . On suppose que uα “ 2α ´ 1. Alors
uα`1 “ 2uα ` 1 “ 2p2α ´ 1q ` 1 “ 2α`1 ´ 1.
Ainsi, la propriété est héréditaire.
˚ D’après le principe de récurrence, pour tout α P N˚ , Jp2α ´ 1q “ 2a ´ 1.
‚ De la même façon, en posant vα “ Jp2α q,
vα`1 “ Jp2α`1 q “ 2Jp2α q ´ 1 “ 2vα ´ 1.
De nouveau, il s’agit d’une suite arithmético-géométrique. On va comme dans la question précédente calculer
les premières valeurs :
v1 “ Jp2q “ 1, v2 “ 1, v3 “ 1
Une récurrence triviale assure que vα “ Jp2α q “ 1 pour tout α P N˚
4. ‚ Existence : soit n P N˚ . La suite p2a qaPN étant strictement croissante et de limite `8, et n ď 20 il existe un
entier α tel que
2α ď n ă 2α`1 .
En effet, sinon, on montre facilement par récurrence que pour tout α P N, 2α ď n, ce qui contredirait la
limite infinie.
On pose alors, ℓ “ n ´ 2α . On a donc
0 ď ℓ ă 2α`1 ´ 2α “ 2α , donc: ℓ P v0, 2α ´ 1w .

D’où l’existence de α P N et de ℓ P v0, 2α ´ 1w tels que n “ 2α ` ℓ.

‚ Unicité : Si n “ 2α ` ℓ, avec ℓ P v0, 2α ´ 1w, alors
2α ď n ă 2α ` 2α “ 2α`1 .
Comme la suite p2α q est strictement croissante, un tel encadrement ne peut être vérifier que pour au plus
une valeur de α. D’où l’unicité de α. Or, α détermine ℓ, d’où aussi l’unicité de ℓ. On en déduit l’unicité de
la décomposition sous la forme de l’énoncé.

8
 5. On raisonne par récurrence forte sur n, en définissant, pour tout n P N˚ , la propriété :
Ppnq : Jpnq “ 2ℓ ` 1, où pα, ℓq est l’unique couple associé à n tel que dans la question précédente.
‚ Initialisation : Le cas n “ 1 est immédiat (et est un cas particulier de la question 3).
‚ Soit n ą 1 telle que Ppmq soit satisfaite pour tout m P v1, n ´ 1w. Soit pα, ℓq le couple associé à n. Puisque
n ą 1, α ě 1. De plus, on pose
ℓ “ 2k ` ε
la division euclidienne de ℓ par 2, avec ε P t0, 1u. Ainsi,

n “ 2m ` ε,

où
m “ 2α´1 ` k.
Or, k P 0, 2 , donc pα ´ 1, kq est le couple associé à m, et d’autre part, m P v1, n ´ 1w. On peut donc
0 α´1 8

appliquer l’hypothèse de récurrence :

Jpmq “ 2k ` 1.
On retrouve alors Jpnq avec les relations obtenues dans la question 1 :
˚ Si ε “ 0,
Jpnq “ Jp2mq “ 2Jpmq ´ 1 “ 2p2k ` 1q ´ 1 “ 4k ` 1 “ 2ℓ ` 1;
˚ Si ε “ 1,
Jpnq “ Jp2m ` 1q “ 2Jpmq ` 1 “ 2p2k ` 1q ` 1 “ 4k ` 3 “ 2ℓ ` 1.
Ainsi, Ppnq est satisfaite.
‚ On déduit du principe de récurrence forte que Ppnq est vraie pour tout n P N˚ .
6. Si pc0 , . . . , ck q est la décomposition en base 2 de n, on a ck “ 1 et
k´1
ÿ k´1
ÿ
n “ 2k ` ci 2 i ď 2 k ` 2i “ 2k ` 2k ´ 1 ă 2k`1 .
i“0 i“0

On en déduit que le couple pα, ℓq associé à n par la question 4 est défini par
k´1
ÿ
α“k et ℓ“ ci 2 i .
i“0

Ainsi,
k´1
ÿ k´1
ÿ k
ÿ
Jpnq “ 2ℓ ` 1 “ 2 ci 2 i ` 1 “ ci 2i`1 ` 1 “ 1 ` ci´1 2i .
i“0 i“0 i“1

Il s’agit du nombre dont les chiffres en base 2 sont obtenus de ceux de n en oubliant le chiffre de poids fort (ck )
et en décalant tous les autres en ajoutant un chiffre 1 en poids faible. Ainsi, si

2
n “ ck ck´1 . . . c0 2 , alors Jpnq “ ck´1 . . . c0 1 .

Dans cette écriture, les premiers chiffres peuvent être nuls. Pour obtenir la décomposition en base 2 avec écriture
unique comme dans la partie II, il faut au préalable supprimer les 0 initiaux. Mais c’est un détail.
7. Trouvons la décomposition en base 2 de n “ 41 :
2
n “ 41 “ 32 ` 8 ` 1 “ 101001 .

On en déduit que
2
Jp41q “ 010011 “ 1 ` 2 ` 16 “ 19 .
C’est bien le résultat qu’on avait trouvé dans la partie I.

Partie IV – Des récurrences plus générales

1. Première méthode d’explicitation

(a) On comprend assez bien ce qui se passe en considérant la décomposition en base 2 :

9
 ‚ Pour pγ, β1 , β2 q “ p1, 0, 0q, Ap2n ` εq “ 2Apnq, pour tout ε P t0, 1u. Ainsi, la décomposition en base
deux de Ap2n ` εq est obtenue de celle de Apnq en rajoutant un 0. De plus n a un chiffre de moins que
2n dans la décomposition en base 2. On peut itérer ce procédé, en perdant un chiffre en base 2 (chaque
chiffre perdu est remplacé par un 0 à la fin de la décomposition), jusqu’à se ramené à un seul chiffre
(donc Ap1q, qui vaut 1). On aura donc
2
Apnq “ 10 . . . 0 ,
le nombre de 0 étant égal à α. Donc Apnq “ 2α , où α est défini comme précédemment.
Si on veut ensuite rendre les choses plus rigoureuses, on peut faire une récurrence forte sur n, facilement
initialisée pour n “ 1. L’hérédité découle facilement du fait que si α est l’exposant associé à une valeur
n, α ´ 1 est associé au quotient de la division de n par 2.
‚ De même si pγ, β1 , β2 q “ p0, 1, 0q, à chaque fois que le dernier chiffre de n est 0, on obtient Bpnq en
considérant l’image par B de l’entier dont la décomposition en base 2 est celle de n amputée de son
dernier chiffre, et en ajoutant un dernier chiffre, complémentaire du dernier chiffre de n. Ainsi, au fur et
à mesure de la réduction, on remplace successivement les chiffres de n par leur complément à 1, jusqu’à
se ramener à Bpcα q “ Bp1q “ 0. Ainsi, ce chiffre est également remplacé par son complémentaire. Par
conséquent, si
α
ÿ
n“ ci 2 i ,
i“0
on obtient α
ÿ
Bpnq “ p1 ´ ci q2i “ p2α`1 ´ 1q ´ n.
i“0
Là encore, la récurrence se fait bien une fois la relation devinée :
˚ L’initialisation pour n “ 1 donne bien Bp1q “ p21 ´ 1q ´ 1 “ 0.
˚ Si pour une valeur de n ą 1, l’égalité est vérifiée pour tout m ă n, on écrit alors n “ 2m ` ε. On a
donc
Bpnq “ 2Bpmq ` 1 ´ ε.
Or, si α est l’exposant associé à n (i.e. l’exposant le plus fort dans sa décompoisition en base 2), α ´ 1
est celui associé à m. Ainsi, par hypothèse de récurrence,

Bpnq “ 2pp2α ´ 1q ´ mq ` 1 ´ ε “ 2α`1 ´ 2m ´ 1 ´ ε “ p2α`1 ´ 1q ´ n.

D’où Ppnq.
˚ D’après le principe de récurrence forte, on a donc B”pnq “ 2α`1 ´ 1 ´ n pour tout n P N, α étant
l’exposant de plus haut degré de la décomposition de n en base 2.
‚ Le troisième cas est similaire, mais sans inversion des chiffres lors de la phase de réduction. Ainsi, on
reporte petit à petit les chiffres de n, jusqu’à se retrouver avec Cpcα q qui vaut 0. Ainsi, le premier chiffre
(de poids α) est remplacé par 0, les autres sont conservés. On obtient donc, toujours avec les mêmes
notations, Cpnq “ n ´ 2α . Encore une fois, la récurrence ne pose pas de problème une fois l’expression
devinée. Je vous la laisse.
(b) On montre par récurrence forte que pour tout n P N˚ ,

f pnq “ γApnq ` β0 Bpnq ` β1 Cpnq.

‚ Initialisation pour n “ 1 :

f p1q “ γ “ γ ¨ 1 ` β0 ¨ 0 ` β1 ¨ 0 “ γsAp1q ` β0 Bp1q ` β1 Cp1q.

‚ Hérédité. Soit n ą 1 tel que la relation soit satisfaite pour tout m P v1, n ´ 1w.
˚ Si n est pair, on écrit n “ 2m. On a alors

f pnq “ 2f pmq ` β0 “ 2γApmq ` β0 p2Bpmq ` 1q ` 2β1 Cpmq

“ γAp2mq ` β0 Bp2mq ` β1 Cp2mq
“ γApnq ` β0 Bpnq ` β1 Cpnq,

par définition de A, B et C.
˚ De même, si n est impair, n “ 2m ` 1,

f pnq “ 2f pmq ` β1 “ 2γApmq ` 2β0 Bpmq ` β1 p2Cpmq ` 1q

“ γAp2m ` 1q ` β0 Bp2m ` 1q ` β1 Cp2m ` 1q
“ γApnq ` β0 Bpnq ` β1 Cpnq.

10
 ‚ Ainsi, d’après le principe de récurrence forte, pour tout n P N˚ ,

f pnq “ γApnq ` β0 Bpnq ` β1 Cpnq .

(c) La relation de III-5 s’obtient avec γ “ 1, β0 “ ´1 et β1 “ 1. On a alors, pour tout n P N˚ :

f pnq “ Apnq ´ Bpnq ` Cpnq “ 2α ´ p2α`1 ´ 1 ´ nq ` pn ´ 2α q “ 2n ` 1 ´ 2α`1 “ 2pn ´ 2α q ` 1 “ 2ℓ ` 1 .

2. Deuxième méthode d’explicitation

(a) La démonstration précédente ne nécessite que de connaître l’existence de pApnqq, pBpnqq et pCpnqq telles que
dans IV-1(a), sans avoir besoin de connaître leur explicitation. Or, les relations peuvent se réécrire (pour A
par exemple) #
Ap1q “ 1
@n ě 2, Apnq “ 2A n2 .
`X \˘

C’est une relation de récurrence de type classique, définissant chaque terme successivement en fonction des
précédents. Cela définit bien sans ambiguïté la suite pApnqq, par récurrence forte, indépendante de γ, β0 et
β1 .
De la même manière, B vérifie les relations :
#
Bp1q “ 0
@n ě 2, Apnq “ 2A n2 ` εn ,
`X \˘

où εn “ 0 si n est impair, et εn “ 1 si n est pair. Ceci est encore une relation de récurrence forte permettant
de définir pBpnqqnPN entièrement et sans ambiguïté, indépendamment de γ, β0 et β1 .
C’est encore la même chose pour pCpxqq en échangeant les parités dans la définition de pεn q.
Ainsi, de telles suites associés à ces jeux de paramètre existent, puis on peut terminer de la même manière
qu’en IV-1(b) pour montrer que pour tout n P N,

f pnq “ γApnq ` β0 Bpnq ` β1 Cpnq .

La grande différence avec IV-1, c’est qu’on ne connaît pas explicitement ces trois suites à ce stade.
(b) ‚ Pour tout n “ 2m ` ε, (ε P t0, 1u) :

f1 pnq “ 1 “ 2f1 pmq ´ 1.

De plus, f1 p1q “ 1. Ainsi, f1 vérifie la relation de récurrence, avec les paramètres p1, ´1, ´1q .
‚ Pour tout n “ 2m ` ε, (ε P t0, 1u) :

f2 pnq “ n “ 2m ` ε “ 2f pmq ` ε,

et f2 p1q “ 1. Donc f2 vérifie la relation de récurrence, avec les paramètres p1, 0, 1q .

(c) J est associée aux paramètres p1, ´1, 1q. Soit n P N˚ , on a donc un système :
$
&1 “ Apnq ´ Bpnq ´ Cpnq
’
n “ Apnq ` Cpnq
’
Jpnq “ Apnq ´ Bpnq ` Cpnq.
%

En faisant la différence de la dernière et de la première équation, on obtient

1 1
Cpnq “ pJpnq ´ 1q “ p2ℓ ` 1 ´ 1q “ ℓ “ n ´ 2α
2 2
On en déduit A par la deuxième équation :

Apnq “ n ´ Cpnq “ 2α .

La valeur de B est obtenue à partir de la première équation :

Bpnq “ Apnq ´ Cpnq ´ 1 “ 2α ´ n ` 2α ´ 1 “ 2α`1 ´ n ´ 1 .

11
3. Description sur la représentation binaire
2
On prouve par récurrence forte sur n “ 1bα´1 . . . b0 que
2 2
f p1bα´1 . . . b0 q “ γβbα´1 . . . βb1 βb0 .

‚ Pour n “ 1,
f pnq “ α “ α2 .
‚ Supposons que pour une valeur donnée n ě 2, l’identité soit vérifiée pour tout m P v1, n ´ 1w. On pose
n “ 2m ` ε, avec ε P t0, 1u. On a alors :

f pnq “ 2f pmq ` βε .

Or, si
2
n “ 1bα´1 . . . b0 ,
on a alors :
2
m “ 1bα´1 . . . b0 et ε “ β0 .
On déduit de l’hypothèse de récurrence applquée à m que
2
f pnq “ 2γβbα´1 . . . βb1 βb1 ` βb0
2
“ γβbα´1 . . . βb1 βb1 0 ` βb0
2
“ γβbα´1 . . . βb1 βb1 βb0

‚ D’après le principe de récurrence forte, pour tout n P N˚ ,

2 2
f p1bα´1 . . . b0 q “ γβbα´1 . . . βb1 βb0 .

12