LICENCE O.M.I. - T.D. Induction
Corrigé

Exercice 1 On rappelle que les nombres de Fibonacci sont définis par F_n= F_n-1 + F_n-2 pour n>1 et F₀= 0, F₁= 1.

On va démontrer par récurrence sur n>0 un certain nombre d'égalités. Puisque l'on considère n>0, le cas de base des récurrences sera n=1.

1) Àmontrer : F₁+F₃+···+F_2n-1 = F_2n

Cas de base : n=1.
On a F₁+ .. + F_2n-1 = F₁= 1 = 0 + 1 = F₀+ F₁= F₂= F_2n.
Hypothèse de récurrence : on suppose que pour un certain n>0, on a F₁+ .. + F_2n-1 = F_2n. Montrons que le résultat reste vrai pour n+1.
On a, F₂(n+1) = F_2n+2 = F_2n+1 + F_2n. Par hypothèse d'induction, F_2n = F₁+ .. + F_2n-1. Comme 2n+1 = 2(n+1)-1, on a bien F₂(n+1) = F₁+ .. + F_2n-1 + F_2(n+1)-1.

2) Àmontrer : F_n+1F_n-1-F_n²=(-1)ⁿ

Cas de base : n=1.
F₂. F₀- F₁²= 1.0-1 = -1 = (-1)¹

Hypothèse de récurrence : F_n+1.F_n-1-F_n²=(-1)ⁿ.
On a

F_(n+1)+1.F_(n+1)-1-F_n+1²	=	F_n+2.F_n-F_n+1²
	=	(F_n+1+F_n).F_n- F_n+1²	par déf. de F_n+2
	=	F_n²+ F_n.F_n+1 - F_n+1²	en développant
	=	F_n²+ F_n+1(F_n- F_n+1)	en factorisant
	=	F_n²+ F_n+1(F_n- F_n-1 - F_n)	par déf. de F_n+1
	=	F_n²- F_n+1.F_n-1	en simplifiant
	=	-(F_n+1.F_n-1 - F_n²)	en jouant avec les signes
	=	-(-1)ⁿ	par hypothèse de récurrence
	=	(-1)ⁿ⁺¹

3) Àmontrer : F₁²+F₂²+···+F_n²= F_nF_n+1

Cas de base : F₁²= 1 = F₁.F₂
Hypothèse de récurrence : F₁²+F₂²+···+F_n²= F_n.F_n+1. Montrons que F₁²+F₂²+···+F_n²+F_n+1²= F_n+1.F_n+2.

F₁²+F₂²+···+F_n²+F_n+1² = F_n.F_n+1+F_n+1² par hypothèse de récurrence

= F_n+1.(F_n+F_n+1) factorisation

= F_n+1.F_n+2 par déf.

4) Àmontrer : F_3n est pair.

Cas de base : F₃= 1 = F₁+F₂= 2 et 2 est pair.
Hypothèse de récurrence : F_3n est pair. Montrons que F_3(n+1) est également pair.

F_3(n+1) = F_3n+3

= F_3n+2 + F_3n+1 par déf. de F_3n+3

= (F_3n + F_3n+1) + F_3n+1 par déf. de F_3n+2

= F_3n + 2F_3n+1
Par hypothèse de récurrence, F_3n. Comme 2F_3n+1 est pair et que la somme de deux entiers pair est un nombre pair, on a que F_3(n+1) est pair.

5) Soit j = 1+sqrt(5)/ 2, àmontrer : j ^n-2£ F_n£j ^n-1.
NB : on utilise une récurrence totale oùl'hypothèse a la forme : pour tout n', si n'£ n alors ....

Cas de base : n=1. Il faut montrer que j ^-1 £ F₁£ j ¹. On vérifie facilement que 2/ 1+sqrt(5)£ 1 et 1£ 1+sqrt(5)/ 2.
Hypothèse de récurrence : pour tout n', si n'£ n alors j ^n-2£ F_n et F_n£j ^n-1. Montrons a) j ^n-1£ F_n+1 et b) F_n+1£ j ⁿ.
Remarquons au préalable que j ²=(1+j ).
- a) En appliquant l'hypothèse de récurrence àF_n et F_n-1 (qui sont chacun inférieur ou égal àn) on a les deux inégalités :
  
  j ^n-3 £ F_n-1
  
  j ^n-2 £ F_n
  Comme toutes les valeurs sont positives, on obtient par sommation :
  j ^n-3 + j ^n-2 £ F_n-1 + F_n
  c'est àdire :
  j ^n-3(1+j ) £ F_n+1
  et, en tenant compte de la remarque préalable :
  j ^n-1 £ F_n+1
- b) De façon analogue, en utilisant l'hypothèse de récurrence pour n-1 et n on obtient que
  F_n-1 + F_n£ j ^n-2+j ^n-1
  Ce qui, compte tenu de la remarque préalable donne bien que F_n+1 £ j ^n-1.

Exercice 2 Le but de cet exercice est de montrer qu'il ne faut jamais oublier létude du cas de base dans une démonstration par récurrence.

1) Étude de la propriétéP(n) := 9 | 10ⁿ-1 avec nÎIN et 9 | 10ⁿ-1 º $ k.10ⁿ-1=9k .

a) On montre la validitédu pas de récurrence, c'est-à-dire la validitéde la formule : " nÎ IN. P(n)Þ P(n+1).
Supposons donc qu'il existe k tel que 10ⁿ-1=9k. On a que 10ⁿ⁺¹-1 = 10ⁿ⁺¹-10+10-1 = 10(10ⁿ-1)+10-1 = 10(10ⁿ-1)+9. Or, par hypothèse, il existe k tel que 10ⁿ-1=9k. D'où10ⁿ⁺¹-1 = 10(9k)+9 = 9(10k+1). Il existe donc k'=10k+1 tel que 10ⁿ⁺¹-1 = 9k' ce nous donne P(n+1).

b) On vérifie facilement que P(0) puisque 10⁰-1 = 0 = 9.0.

c) On peut donne légitimenent déduire que " nÎIN. P(n).

2) Étude de Q(n) := 9 | 10ⁿ+1.

a) On montre, làaussi la validitéde pas de récurrence : " nÎIN. Q(n)Þ Q(n+1).
Supposons k tel que 10ⁿ+1 = 9k. En remarquant que 10ⁿ⁺¹+1 = 10(10ⁿ+1)-9, on obtient Q(n+1).

b) En revanche, on ne peut trouver aucun entier m tel que Q(m). Si m=0, on a 10⁰+1 = 2 qui n'est pas divisible par 9. On peut même montrer que pour tout nÎIN, 10ⁿ+1 mod 9 = 2.
Par induction sur n

Cas de base : cf supra
Hypothèse de récurrence : 10ⁿ+1 mod 9 = 2. Montrons 10ⁿ⁺¹+1 mod 9 = 2.
Par hypothèse de récurrence et définition du modulo, il existe k telque 10ⁿ+1 = 9k+2. On a : 10ⁿ⁺¹+1 = 10(10ⁿ+1)-9 = 10(9k+2)-9 = 9(10k+1)+2. D'oùle résultat escompté.

c) Même si le pas de récurrence est valide (Q(n)Þ Q(n+1)), il ne suffit pas àlui seul àconclure que " nÎIN. Q(n) puisque l'on ne peut jamais << amorcer la pompe >> de la récurrence.

3) Étude de R(n) := 3| 4ⁿ+7ⁿ

a) Montrons R(n)Þ R(n+1).
Posons A_n= 4ⁿ+7ⁿ et supposons que 3| 4ⁿ+7ⁿ pour un certain n. On remarque que A_n+1-A_n= 3.(4ⁿ+2.7ⁿ). Par hypothèse, il existe k tel que A_n= 3.k, d'oùA_n+1 = 3.(4ⁿ+2.7ⁿ+k), i.e. R(n+1).

b) Comme pour Q(n), il n'existe aucun entier n satisfaisant R(n). En fait, on peut montrer que A_nmod 3 = 2, pour tout nÎIN.

Exercice 3 Pour donner une définition récursive de f(n) = a^2ⁿ, il faut savoir exprimer a^2ⁿ⁺¹ en fonction de a^2ⁿ. C'est le sens de l'indication : << On pourra remarquer que a^2ⁿ⁺¹=(a^2ⁿ)². >>

Il est alors trivial de donner la définition récursive de f :

ì
í
î

f(0)	=	a
f(n+1)	=	f(n)²

Exercice 4 Une définition récursive qui réclame 4 cas de base et un pas de 4.

1) En développant l'expression (n+1)²-(n+2)²-(n+3)²+(n+4)², on obtient :

(n+1)²-(n+2)²-(n+3)²+(n+4)²	=	n²+1+2n-n²-4-4n-n²-9-6n+n²+16+8n
	=	4

2) On veut établir que " mÎIN $ nÎIN. m = S_i=1ⁿe_ii² avec e_iÎ {1, -1}. On procéde par récurrence sur m en considérerant 4 cas de base.

a) si m=0, on prend n=7 et on a 0=1²+2²-3²+4²-5²-6²+7².
b) si m=1, on prend n=1 et on a 1=1².
c) si m=2, on prend n=4 et on a 2=-1²-2²-3²+4².
d) si m=3, on prend n=2 et on a 3=-1²+2².
e) Étapde de récurrence : supposons que qu'il existe n tel que S_i=1ⁿe_ii² et montrons que $ nÎIN. S_i=1ⁿ⁺⁴ e_ii².
Par hypothèse de récurrence, on sait que m = S_i=1ⁿe_ii². En utilisant 1), on peut écrire m+4 = S_i=1ⁿe_ii²+n+1)²-(n+2)²-(n+3)²+(n+4)². En posant n'=n+4 on a donc montréqu'il existe n' tel que m+4 = S_i=1^n' e_ii².

Remarque : on a bien un résultat valide surtout les entiers puisqu'il est vari des 4 premiers et que tout entiers m > 3 peut s'écrire sous la forme m'+4.

Exercice 5 On rappelle la définition (inductive) de l'ensemble des arbres binaires étiquetés :

Ø est un arbre.
si a est une étiquette et si t₁ et t₂ sont des arbres alors t=(a,t₁,t₂) est un arbre.

On appelle feuille un arbre de la forme (a,Ø,Ø).

n(t) Le nombre de noeuds d'un arbre est le nombre d'étiquette qu'il contient. On les compte récursivement ainsi :

ì
í
î

n(Ø) = 0

n(a,t₁,t₂) = 1+n(t₁)+n(t₂)
ar(t) Le nombre d'arêtes s'onbtient de façon analogue en comptant 2 chaque fois que l'on descend récursivement :

ì
í
î

ar(Ø) = 0

ar(a,t₁,t₂) = 2+ar(t₁)+ar(t₂)
h(t) La hauteur d'un arbre est la longueur maximale obtenue en comptant 1 chaque fois que l'on descend récursivement :

ì
í
î

h(Ø) = 0

h(a,t₁,t₂) = 1+max(h(t₁),h(t₂))
f(t) Le nombre de feuille est le nombre de sous arbres de la forme (a,Ø,Ø). Pour les compter, il faut ici aussi descendre récursivement dans l'arbre, mais s'arréter dés que l'on trouve une feuille :

ì
í
î

f(Ø) = 0

f(a,Ø,Ø) = 1

f(a,t₁,t₂) = f(t₁)+f(t₂)

Remarque : la définition de f donne f(Ø) = 0, ce qui premet de compter correctement le nombre de feuilles d'un arbre de la forme f(a,Ø,t) oùt¹Ø.

Exercice 6 La définition inductive de l'ensemble des arbres donne le principe de raisonnement par récurrence suivant : si t est un arbre, pour montrer P(t), on montre :

Cas de base : P(Ø).
Étape de récurrence : on suppose P(t₁) et P(t₂) pour montrer que P(a,t₁,t₂) pour une étiquette a quelconque.

1) Montrons, selon ce principe, que n(t) £ 2^h(t)-1 où n(t) et h(t) sont les fonctions définies àl'exercice précédent.

Cas de base : il faut montrer que n(Ø) £ 2^h(Ø)-1, c'est-à-dire, par définition de n et h : 0 £ 2⁰-1. Ce qui est immédiat.
Soit t=(a,t₁,t₂). Supposons que n(t₁) £ 2^h(t₁)-1 et que n(t₂) £ 2^h(t₂)-1. Il faut montrer que n(t) £ 2^h(t)-1.
Remarquons que, par définition de h (et de max), on a h(t₁) £ h(t)-1 et h(t₂) £ h(t)-1. En utilisant les hypothèses de récurrence et les deux inégalités remarquées, on obtient par sommation que n(t₁)+n(t₂) £ 2^h(t)-1 + 2^h(t)-1 -2. D'où, en utilisant l'égalitén(a,t₁,t₂)=n(t₁)+n(t₂)+1 et en simplifiant : n(t) £ 2.2^h(t)-1 - 1 = 2^h(t)-1.

2) Montrons f(t) £ 2^h(t)-1. Le principe de récurrence suit ici le principe de définition de f avec deux cas de base (Ø et (a,Ø,Ø)).

Premier cas de base : il faut montrer que f(Ø) £ 2^h(Ø)-1, c'est-à-dire 0 £ 2^-1. Ce qui est vrai.
Second cas de base : il faut montrer que f(a,Ø,Ø) £ 2^h(a,ØØ,)-1, c'est-à-dire 1 £ 2^1-1. Ce qui est également vrai.
Étape récursive : on pose t=(a,t₁,t₂) et on suppose que f(t₁) £ 2^h(t₁)-1 et que f(t₂) £ 2^h(t₂)-1.
En utilisant les inégalités remarquées ci-dessus et les hypothèses de récurrence, on obtient que f(t₁)£ 2^{max(h(t₁),h(t₂))-1} et f(t₂)£ 2^{max(h(t₁),h(t₂))-1}. Par sommation, définition de f et simplification, on a f(t)£ 2^{max(h(t₁),h(t₂))}. Comme max(h(t₁),h(t₂))=h(t)-1, on a bien que f(t)£ 2^h(t)-1.

Exercice 7 Un arbre binaire est strict si chacune de ses branche se termine par une feuille. On n'a donc pas de sous arbre de la forme (a,Ø,t₂) avec t₂¹Ø ni (a,t₁,Ø) avec t₁¹Ø.

1) Inductivement, cela signifie que le cas de base des arbres strict sont les feuilles. D'oùla définition :

pour toute étiquette a, l'arbre (a,Ø,Ø) est strict.
si t₁ et t₂ sont des arbres binaires stricts alors (a,t₁,t₂) l'est aussi, quelque soit a.

Remarquons que les arbres binaires stricts ainsi définis ne sont jamais vides, au sens des arbres binaires. Du coup, il faut amender un peu les définitions des fonctions n, a et f de l'exercice 5. Pour éviter toute équivoque, on notera (a) pour (a,Ø,Ø). Ainsi, le symbole Ø ne fait plus partie de notre langage. Et le cas de base des récurrence est t=(a).

ì
í
î

n(a)	=	1
n(a,t₁,t₂)	=	1+n(t₁)+n(t₂)

ì
í
î

ar(a)	=	0
ar(a)	=	2+ar(t₁)+ar(t₂)

ì
í
î

h(a)	=	1
h(a,t₁,t₂)	=	1+max(h(t₁),h(t₂))

ì
í
î

f(a)	=	1
f(a,t₁,t₂)	=	f(t₁)+f(t₂)

2) Montrons que n(t) = ar(t)+1 oùn. On procède selon le principe de récurrence induit par la définition.

Case de base : t=(a). On vérifie facilement que n(a) = ar(a)-1.
On suppose que n(t₁) = ar(t₁)+1 et n(t₂) = ar(t₂)+1. On en déduit que n(t) = ar(t₁)+ar(t₂)+3 = ar(t)+1.

3) Montrons que n(t) = 2.f(t)-1.

Case de base : t=(a). On vérifie facilement que n(a) = 1 = 2-1 = 2.f(a)-1.
On pose t=(a,t₁,t₂) et on suppose que n(t₁) = 2.f(t₁)-1 et n(t₂) = 2.f(t₂)-1. On a alors n(t) = n(t₁)+n(t₂)+1 = 2.f(t₁)+2.f(t₂)-1 = 2.f(t)-1.

Exercice 9 Les arbres équilibrés restreignent à1 au maximum la différrence de hauteurs entre les sous-arbres immédiats (les arbres t₁ et t₂ sont les sous-arbres immédiats de (a,t₁,t₂)).

1) On définit inductivement l'ensemble AVL des arbres biniares équilibrés par les deux clause suivantes :

ØÎ AVL.
si t₁, t₂Î AVL et |h(t₁)-h(t₂)| £ 1 alors (a,t₁,t₂)Î AVL.

Commentaires : la restriction imposée par la définition àt₁ et t₂ doit se retrouver dans le principe de récurrence induit. L'étape de récurrence du raisonnement sur les AVL se formalise ainsi

" t₁,t₂Î AVL. |h(t₁)-h(t₂)| £ 1 Ù P(t₁) Ù P(t₂) Þ P(a,t₁,t₂)

2) On définit la suite (u_n)_nÎIN

u₀= 0

u₁= 1

u_n+2 = u_n+1+u_n+1

Montrons, par induction sur l'arbre équilibrét, que n(t) ³ u_h(t). Comme la suite (u_n) est définie avec deux cas de base, nous considérons les arbres de hauteurs 0 puis les arbres de hauteur 1 avant d'envisager l'étape de récurrence. Pour être précis, nous raisonnerons donc par récurrence sur la hauter de t.

Si h(t)=0 alors t=Ø, on a n(Ø)=0=u₀=u_h(Ø).
Si h(t)=1 alors, nécessairement, par définition des AVL, t=(a,Ø, Ø) ; alors, n(t) = 1 = u₁= u_h(t).
Si h(t)>1, soient t₁, t₂Î AVL tels que|h(t₁)-h(t₂)| £ 1, n(t₁) ³ u_h(t₁) et n(t₂) ³ u_h(t₂). Soit t=(a,t₁,t₂), il faut montrer que n(t) geq u_h(t).
Par définition de n et hypothèses de récurrence, on a que

n(t) = n(t₁)+n(t₂)+1 ³ u

h(t₁)
+u

h(t₂)
+1 (1)
On raisonne alors par cas selon que h(t₁) > h(t₂), h(t₁) = h(t₂) ou h(t₂) > h(t₁) :
- si h(t₁) > h(t₂) alors, par définition de h et max, h(t) = h(t₁)+1 et, par définition des AVL, h(t₂)=h(t₁)-1. D'oùh(t₁) = h(t)-1 et h(t₂) = h(t)-2. En remplaçant h(t₁) et h(t₂) dans (1), on obtient n(t) ³ u_h(t)-1+u_h(t)-2+1 = u_h(t).
- si h(t₂) > h(t₁), on raisonne de façon analogue au cas précédent en inversant les rôles de t₁ et t₂.
- si h(t₁) = h(t₂) alors, par définition de h et max, on obtient h(t₁) = h(t₂) = h(t)-1. En utilisant (1), on a n(t) ³ u_h(t)-1+u_h(t)-1+1. Comme la suite (u) est croissante, u_h(t)-1³ u_h(t)-2. D'oùn(t) ³ u_h(t)-1+u_h(t)-1+1³ u_h(t)-1+u_h(t)-2+1= u_h(t)

Exercice 11 On rappelle que le monoïde libre A^* est l'ensemble des mots construits sur un alphabet A par l'opération associative de concaténation (notée ·) avec le mot vide pour élément neutre (notée). On confond une lettre de l'aphabet A avec le mot forméde cette seule lettre a, ce qui autorise les écritures a· w et w· a oùaÎ A et wÎ A^*.

Dés lors, la définition de l'opération miroir est triviale :

mir(w) =

ì
í
î

e	si w=e
mir(v)· a	si w=a· v

Exercice 12 Définition inductive de l'ensemble L des listes d'élements de d'un alphabet A :

eÎ L.
si aÎ A et xÎ L alors (ax)Î L

La liste (ax) est obtenue par ajout de a devant x. On dit que l'on préfixe x avec la lettre a. Il ne faut pas confondre cette opération avec la concaténation de l'exercice précédent. L'expression (xa) n'a pas de sens ! La liste constituée des lettres a₁, a₂ et a₃, dans cet ordre, s'écrit : (a₁(a₂(a₃e))). On pourra écrire (a) simplement en place de (ae).
On a sur L le principe de récurrence suivant :

Cas de base : P(e).
Étape de récurrence : " aÎ A " xÎ L. P(x)Þ P(ax)

Soit g : L× L® L définie par :

ì
í
î

g(e, y)	=	y
g((ax), y)	=	g(x, (ay))

1) Montrons pas récurrence sur xÎ L que " yÎ L.g(x,y)Î L (ce qui revient àdire que g(x,y) est partout définie sur L.)

Si x=e, soit yÎ L, on a g(e, y) = yÎ L.
Si x=(az) avec zÎ L. Il faut montrer que " yÎ L. g((az),y)Î L. Soit donc yÎ L, montrons g((az),y)Î L. C'est-à-dire g(z,(ay))Î L.
On a , par hypothèse de récurrence " yÎ L. g(z,y). On a donc, en particulier que g(z,(ay))Î L.

2) g((a₁),y)=g(e,(a₁y))=(a₁y)

3) Pour être précis, il faut montrer " yÎ L. g((a_n(a_n-1(..(a₁)..))),y) = g(e,(a₁(..(a_n-1(a_ny))..))), par récurrence sur n > 0.

Si n=1, voir question précédente.
Supposons donc " yÎ L. g((a_n(a_n-1(..(a₁)..))),y) = g(e,(a₁(..(a_n-1(a_ny))..))) il faut montrer que
" yÎ L. g((a_n+1(a_n(..(a₁)..))),y) = g(e,(a₁(..(a_n(a_n+1y))..))).
Par définition, g((a_n+1(a_n(..(a₁)..))),y)= g((a_n(..(a₁)..)),(a_n+1y)). En particularisant y à(a_n+1y) dans l'hypothèse de récurrence, on obtient l'égalitérecherchée.

4) Si rev(x) = g(x,e), en utilisant le résultat de la question précédente, et la définition de g, on obtient rev((a₁(..(a_n)..))) = (a_n(..(a₁)..)).

This document was translated from L^AT_EX by H^EV^EA.

F₁²+F₂²+···+F_n²+F_n+1²	=	F_n.F_n+1+F_n+1²	par hypothèse de récurrence
	=	F_n+1.(F_n+F_n+1)	factorisation
	=	F_n+1.F_n+2	par déf.

F_3(n+1)	=	F_3n+3
	=	F_3n+2 + F_3n+1	par déf. de F_3n+3
	=	(F_3n + F_3n+1) + F_3n+1	par déf. de F_3n+2
	=	F_3n + 2F_3n+1

j ^n-3	£	F_n-1
j ^n-2	£	F_n