Voilà un petit tutorial de math générales (pas ce qu´on apprend à l´école) qui pourra servir à tout le monde.
Pour les notations, j´utiliserai:
V3 = racine_carrée(3)
V(5+n) = racine_carrée(5+n)
a^b = a exposant b
LA RECURENCE
Le principe de démonstration par récurence est le suivant:
Pour qu´une affirmation K(n) soit vraie pour tout entier naturel n, il suffit de prouver d´une part que K(0) est vraie (c-à-d prouver qu´elle est vraie pour 0) (c´est ce qu´on appelle le "pas initial"), et d´autre part, il faut essayer de prouver que K(x+1) est vraie en partant du principe que K(x) est vraie (c-à-d supposer que la proposition est vraie pour un certain entier positif x et en déduire de ce fait là quelle est également vraie pour x+1) (c´est ce qu´on appelle le "pas récursif").
Quand on a démontré celà, comme la proposition est vraie pour 0 alors elle est vraie pour 1, puis comme elle est vraie pour 1 elle est vraie pour 2, puis comme elle est vraie pour 2 elle l´est pour 3, et ainsi de suite, elle est vrai pour tout entier naturel n.
note: attention ca ne veut pas dire que la proposition est vraie pour n=oo
note: ce principe peut commencer à un nombre différent de 0: on peut par exemple prendre la pas initial pour n=5, mais alors on n´aura pas prouvé que la proposition est vraie pour les entiers inférieurs ou égaux à 4.
Il existe une autre forme de récurence, qui utilise le fait que la proposition K(n) est vraie pour 0,1,2,3,...,x pour montrer quelle est vraie pour x+1.
Exemple:
La somme des nombres de 1 à n vaut 1+2+3+...+n = n(n+1)/2
Démonstration par récurence:
- Pas initial: on prend le pas initial à n=1.
Pour n=1, il est évident que 1=1(1+1)/2
Supposons que 1+2+3+...+x=x(x+1)/2.
On doit prouver que 1+2+3+...+x+(x+1)=(x+1)(x+2)/2
Or
1+2+3+...+x+(x+1)=x(x+1)/2+(x+1)=(x/2)(x+1)+(x+1)=
((x+2)/2)(x+1)=(x+1)(x+2)/2
CQFD
Ainsi, la proposition étant vraie pour 1, elle devient vraie pour 2, puis pour 3,... donc pour tout entier naturel non nul.
Formules interessantes qui se démontrent par récurence:
1+2+3+...+n = n(n+1)/2
1²+2²+3²+...+n² = 1+4+9+...+n² = n(n+1)(2n+1)/6
1³+2³+3³+...+n³ = 1+8+27+...+n³ = n²(n+1)²/4
1^4+2^4+3^4+...+n^4 = n(n+1)(2n+1)(3n²+3n-1)/30
1^5+2^5+3^5+...+n^5 = n²(n+1)²(2n²+2n-1)/12
La suite de Fibonacci est définie de manière récursive:
F(0) = 0
F(1) = 1
F(n+1) = F(n)+F(n-1)
C´est donc la suite
0,1,1,2,3,5,8,13,21,34,55,89,...
On a la formule
F(n) = (((1+V5)/2)^n - ((1-V5)/2)^n)/V5
LE PRINCIPE DES TIROIRS
Ce principe peut parraitre un peu idiot, mais lorsqu´on l´applique à des problèmes plus vastes, il peut devenir extrèmement puissant:
Si on doit ranger 11 cahussettes dans 5 tiroirs, alors il y a forcément un tiroir qui contient au moins 3 chaussettes.
Si on doit ranger 14 chaussettes dans 5 tiroirs, alors il y a forcément un tiroir qui contient au plus 2 chaussettes.
Pour le dire de façon formelle:
Soient k et n deux entiers positifs.
Si on répartit kn+1 objets dans n boîtes, alors l´une des boîtes contient au moins k+1 objets.
si on répartit kn-1 objets dans n boîtes, alors l´une des boîtes contient au plus k-1 objets.
Exemple:
Dans tout groupe de 25 personnes, au moins 3 ont leur anniversaire le même mois.
En effet, disposer 25 dates sur 12 mois, c´est comme répartir 2*12+1 objets dans 12 boîtes, ce qui implique que l´une des boîtes contient au moins 3 objets, c-à-d que l´un des mois contient au moins 3 anniversaires.
Exercice:
Montrer que si l´on choisit arbitrairement 52 entiers, on peut toujours en trouver 2 tels que leur somme ou leur différence est divisible par 100.
THEORIE DES NOMBRES : LES CRITERES DE DIVISIBILITE
Il est très facile de vérifier à la main que 4547112822928200 est divisible par 2, mais il est beaucoup plus difficile de déterminer s´il est divisible par 7. D´où l´intéret de créer des "critères de divisibilité"...
Un nombre est divisible par 2 si et seulement si (ssi) il est pair (c-à-d s´il termine par 0,2,4,6 ou 8).
Par exemple, 123564555456587898754528 est divisible par 2.
Un nombre est divisible par 3 ssi la somme de ses chiffres est divisible par 3.
Par exemple 2383974576 est divisible par 3 car la somme de ses chiffres est 54 et que la somme des chiffres de 54 est 9 (qui est clairement un multiple de 3).
Un nombre est divisible par 4 ssi ses deux derniers chiffres forment un nombre divisible par 4.
Par exemple 3824001266979613316 est divisible par 4.
Un nombre est divisible par 5 ssi il termine par 0 ou 5.
Par exemple 2122258989870880 est divisible par 5.
Un nombre est divisible par 6 ssi il est divisible par 2 ET par 3.
Par exemple 876874587995498020680126 est divisible par 6 car il est pair et que la somme de ses chiffres est 129 et que la somme des chiffres de 129 est 12 (qui est clairement un multiple de 3).
Un nombre est divisible par 8 ssi ses trois derniers chiffres forment un nombre divisible par 8.
Par exemple 5658701200457256 est divisible par 8.
Un nombre est divisible par 9 ssi la somme de ses chiffres est divisible par 9.
Par exemple 58120344 est divisible par 9 puisque la somme de ses chiffres est 27 (qui est clairement un multiple de 9).
Pour la divisibilité par 7, la méthode est un peu plus compliquée.
Pour déterminer si un nombre N est divisible par 7, il faut procéder de la manière suivante:
On découpe le nombre N entre l´avant-dernier chiffre et le dernier. On soustrait alors 2 fois le chiffres de droite du nombre de gauche. On obtient ainsi un nouveau nombre. Si le nombre N était un multiple de 7, le nouveau nombre que l´on a obtenu est encore un multiple de 7.
On répète cette opération jusqu´à ce que l´on obtienne un nombre pour lequel on voit immédiatement qu´il est multiple de 7.
Par exemple, si N=31759
On découpe: 3175 9
On soustrait deux fois la partie droite de la partie gauche: 3175-2*9 = 3175-18 = 3157
On découpe: 315 7
On soustrait deux fois la partie droite de la partie gauche: 315-2*7 = 315-14 = 301
On découpe: 30 1
On soustrait deux fois la partie droite de la partie gauche: 30-2*1 = 28
Et 28 = 7*4. Donc 31759 est bien un multiple de 7.
Pour savoir si un nombre N est divisible par 11, on fait le calcul suivant:
On prend le premier chiffre de N, on soustrait le deuxième chiffre de N, on ajoute le troisième chiffre de N, on soustrait le quatrième chiffre de N, et ainsi de suite pour tout le nombre. Si le nombre ainsi obtenu est un multiple de 11 (qui peut être négatif), alors est également un multiple de 11.
Par exemple, si N=18273904
On calcule 1-8+2-7+3-9+0-4 = -22
Donc N est un multiple de 11.
THEORIE DES NOMBRES : LE PGCD
Rappel: le pgcd de deux nombres entiers a et b, noté (a,b), est le plus grand entier naturel qui divise a et qui divise b. Le ppcm de deux nombres entiers a et b, noté [a,b], est le plus petit entier naturel divisible par a et divisible par b.
On a une formule très pratique:
Pour tout couple d´entiers naturels a,b on a
(a,b)*[a,b] = a*b
L´algorithme d´Euclide permet de trouver rapidement le pgcd de deux nombre:
Il suffit de répéter l´opération
(a,b) := (b,r) ou r est le reste de la division de a par b.
jusqu´à ce que r=0.
Alors le pgcd initial est égal à b.
Exemple:
(1988,236)=(236,100)=(100,36)=(36,28)=(28,8)=(8,4)
=(4,0)=4
Théorème de Gauss:
Soient a,b,c des entiers naturels.
Si a divise bc et si (a,b)=1, alors a divise c.
Ce théorème peut etre util dans des cas comme celui-ci:
L´énoncé fournit que 7777777 = 239*32543
On voit facilement que 7 divise 7777777, et d´autre part, le calcul du pgcd de 7 et 239 donne (7,239)=1. On peut en conclure que 32543 est divisible par 7.
DIVERSES PROPRIETES D´ARITHMETIQUE
Quand on divise les puissances successives d´un nombre N par un même nombe q, les restes r obtenus apparaissent de façon périodique.
Par exemple, si on calcule les restes successifs des puissances de 2 par 7, on a:
2^0 = 1 = 0*7+1
2^1 = 2 = 0*7+2
2^2 = 4 = 0*7+4
2^3 = 8 = 1*7+1
2^4 = 16 = 2*7+2
2^5 = 32 = 4*7+4
2^6 = 64 = 9*7+1
.
.
.
La suite des restes successifs est ici: 1,2,4,1,2,4,1,2,4,1,2,4,...
Théorème de Bézout:
Si le pgcd de deux entiers a et b est (a,b)=1, alors il est possible de trouver deux entiers m et n tels que an-bm=1
Petit théorème de Fermat:
Si p est un nombre premier et si a est un nombre naturel non multiple de p, alors p divise a^(p-1)-1
Théorème de Wilson:
Si p est un nombre premier, alors p divise (p-1)!+1
EQUATIONS DIOPHANTIENNES
Ce sont des équations de la forme ax+by=c où a,b,c sont des entiers et où l´on cherche les solutions entières pour x et y.
Il faut d´abord regarder si il y a des solutions:
Un condition indispensable est que c soit un multiple du pgcd de a et b. En effet, si par exemple a et b étaient tous les deux des multiple de 5, c doit forcément l´être aussi...
Soit g le pgcd de a et b.
Il faut trouver les deux entiers pet q tels que pa+qb=g.
La solution générale est alors (donnée sous forme paramétrique, de paramètre entier n):
|x=(pc+qn)/g
|y=(qc-pn)/g
exemple: pour résoudre 3x+7y=2 dans les entiers:
g = pgcd(3,7) = 1.
2 est bien un multiple de 1, donc il y a des solutions.
On cherche p et q tels que 3p+7q = 1
On trouve
|p=-2
|q=1
Donc la solution générale est donnée par
|x = (-2*2+1*n)/1 = n-4
|y = (1*2-(-2)*n)/1 = 2n+2
PRINCIPE DES COULEURS
Ce principe consiste à colorier en plusieurs couleurs (souvent noir et blanc suffisent) un quadrillage ou un échiquier, de façon à pouvoir démontrer certaines choses. C´est assez vaste, et on comprend mieux en observant directement un exemple.
D´un échiquier 8x8, on enlève la case suppérieure gauche et la case inférieure droite
Est-il possible de le recouvrir de 31 dominos 1x2 ?
On colorie la figure comme un échiquier (en noir et blanc alterné) en prenant la case suppérieure droite noire.
La figure contient alors 32 cases noires et 30 cases blanches. Mais chaque fois que l´on pose un domino 1x2, on recouvre forcément une case noire et une case blanche. Donc quand on aura posé 30 dominos, toutes les cases blanches seront recouvertes, et il retera 2 cases noires qui ne pourront donc pas être recouverte par le 31ème domino.
Exercice:
On dispose de 20 boîtes et de 20 cartes, numérotées 0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9.
Est-il possible de placer les 20 cartes dans les boîtes, de telle manière qu´il n´y ait qu´une seule carte par boîte et que les cartes portant un même numéro, soit séparées par ce même nombre de boîte (par exemple, les 2 cartes numérotées 3 sont séparées par 3 boîtes) ?
INVARIANTS ET MONOVARIANTS
Cette méthode s´adapte lorsque une opération de modification de qqch est répétée un certain nombre de fois.
Un INVARIANT est une quantité qui ne change pas lors de différentes modifications.
Un MONOVARIANT est une quantité qui évolue de manière monotone lors des différentes modifications.
Exemple:
Un cercle est divisé en 6 secteurs. Les nombres 1,0,1,0,0,0 sont écrits sur les secteurs dans le sens antihorlogique.
A chaque étape, on peut augmenter deux nombres voisins de 1 unité. Est-il possible de rendre égaux les 6 nombres par une suite de telles actions ?
Soient a1,a2,a3,a4,a5,a6 les valeurs des 6 secteurs.
Au départ, on a
a1=1
a2=0
a3=1
a4=0
a5=0
a6=0
On remarque que le nombre a1-a2+a3-a4+a5-a6 est invariant par l´action définie dans l´énoncé.
Or cette valeur est égale à 2 au départ, et l´énoncé demande si l´on peut arriver à une situation ou cette valeur est nulle. Mais comme c´est un invariant, ce n´est donc pas possible.
).
le_duche, je comprends pas tout mais j´y travaille 
avec plaisir 
tu saurais le poster ici ? ca m´interesse !
mais rien n´y faisait alors elle c´etait fait des films sur ma vie privé...