Labo 10
Démontrer
que
2 m n n 4 n 5
0 2 a 5
Cas de base
pour n 5 25 5 52
32 25 ok
Cas induction
Soit Paul Vn 35
If
n 4 on Pln est vra
suppose que
On montre quiators
que
P net est vra auss
P net 2 net
n 1 n 2ntl
comparer 2n 1 avec m n 4
ga induction
prower par
done
m 2nd
be
n4ij n
2 m m
2 2.2 P ypothise
2 2
L 241
Par induction on a n 5
22 m
Ex 13
5
Démontrer
que
2 n n n 4 n
o 2'34 5 6
Cas de base
pour
n b 23 5
32725 OK
Cas inductif
soit Pcn 215kt ns 4 s
n 4 On suppose P n est vra
que
c a d 2 m est vra
que
é montrons alors P ntl est rra ans
qu que
Vn 34 2 net
Objectif
nil
ab a 2raxb b
n e 2 1 n 12
m n
Prowone induction quet
m 2n 1 n 5
[Link] s2 252 2 1
0K
Cas inductif
sen
[Link]
n 2nti n 4
tableau de signe
11
S ntl n 1 2n 3
susaimt
compliqué
2 ntl 2nd
Selon dimo
4nt2
2 2nel
d apre's le
prof si on fail induction
dans une indeon on
peut assumer que
la le est mai
I0
n
h 2 m 2 n 1 du proof ish
response
Ñ 2 4 n 72n
at n s
n 1 22m
On a hypothise
par
2ⁿ m n 2ⁿ
m 22
n 1 0 n 5 α
2
n 1 02 n 2n 11
mn n 1 n
cas de base In 2
2 2 1 2 2 4
224 0K
Cas inductif
Soit Pens n 2n n I
supposons que
Pcn est una n 2 et montrons
que Pinel est aussi vra
P net ntl 2 net An 1
ntl ntl n
Par hypothise n n
ntl nti n n 1 n
o La lb a cb
or on a n n 1
n net
Flors tn [Link]
par hypotheses
n n 1
Ntl nti
1
ntl 2 n 1
Conclusion n 1 n Ln
facultatif
Ex31
Soit la matrice A
A n 2
TAetBdutmatric
Alic Blac il fautque C 12
A A
3 Asa
B
8 BE
A B x
t
ff i
Ode division
us natives
pour
sculement x
n 2 minimum 2
111 EE a 1
9 2 012
[Link]
tquean q ggimntrons
qu alors que
Ant 8
A AA b EE
Renversement
8
840 2 1 000
2
R
000 0111
8 74
ÉÉnu
les couples dans la relations R a b a diviseb
dans tens 1,2 3,4 5,6
T1 T2 53 154 151 1561 5.2 54
2,6 53 56 4,4 5,51 56
b graph
tableau
a
Reflexivite cherche diagonale
[Link] done symmetrique
eR BUT doesn't mean
non symmetrique
2 1 ER doesntexist
a 2,2 2,3 2,4 3,2 3,3 3,4
support ens 1,2 3,4
R Non0011,1 et 4,4 R
2,4 GR mais 4,2 R
S Non on a
AS Non car on a 2,3 e R et 3,2 ER
T Oui
if 5 ERV
Queune
1210 relation qui
1314 L napportant pas
parmis les couples
OK
44 E ER
313 13,2 3 2 GR existant alors
4 la donation est
13,4 0 transitive
b 1,1 1,2 2,1 2,2 3,3 4,4
Ou S onenleve 1 2 et 2.1
a R alors la fat est sym et asym
b Sym Oui 112 et 2,1
a Rb a b
s
c Asym Non
b R a
d s Ska
4 4,2
R
R Non
S Oa
As Non
T
## Relations et Représentations
### Types de Représentation
- Trois méthodes pour représenter une relation :
1. Par couples
2. Par graphes
3. Par tableaux
### Propriétés des Relations
- **Réflexivité** : Une relation est réflexive si chaque élément est en
relation avec lui-même
- **Symétrie** : Si a est en relation avec b, alors b doit être en relation
avec a
- **Anti-symétrie** : Si a est en relation avec b, alors b ne doit pas être en
relation avec a
- **Transitivité** : Si a est en relation avec b et b est en relation avec c,
alors a doit être en relation avec c
### Exemple de Relation
Relation de divisibilité dans l'ensemble {1, 2, 3, 4, 5, 6} :
- Couples : (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,2), (2,4), (2,6), etc.
- Vérification des propriétés :
- Non réflexive : car certains éléments ne sont pas en relation avec eux-
mêmes
- Non symétrique : car si 2 divise 4, 4 ne divise pas 2
- Non anti-symétrique : car il existe des couples symétriques
## Démonstrations par Récurrence
### Structure de la Démonstration
1. Cas de base
2. Hypothèse de récurrence
3. Hérédité