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
*pas récursif:*
Supposons que 1+2+3+...+x=x(x+1)/2 est vrai
On doit en déduire que 1+2+3+...+x+(x+1)=(x+1)(x+2)/2
Or , puisque 1+2+3+...+x=x(x+1)/2
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.


Voici quelques 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

Ce principe peut parraitre un peu idiot, mais lorsqu´on l´applique à des problèmes plus vastes, il peut devenir extrèmement puissant.
L'idée est la suivante:
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.

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 car 80 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 (divisible par 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.

Remarques
Il est parfois facile de vérifier si un nombre est divisible par 1001 et il se trouve que 1001 = 7*11*13. Ainsi, dans certains exercices, on pourra prouver qu'un nombre est divisible par 13 et/ou 7 en prouvant qu'il est divisible par 1001.

Voici quelques notations utiles pour faire des math dans un environnement  qui ne s'y prète pas...

Toute première chose, METTEZ LES PARENTHÈSES pour éviter les ambiguïtés...
Il arrive souvent que des gens écrivent a^b+c pour dire a^(b+c), alorsqu'ils ont écris (a^b)+c... ou encore je vois parfois a+b/c+d pour(a+b)/(c+d)
Les parenthèses sont primordiales pour une bonne compréhension. (il nefaut pas en gaver le texte non plus, sinon on ne voit plus rien du tout...)

"a exposant b"
a^b
mais préférez a² et a³ à a^2 et a^3
exemple:
2^n = 2 exposant n
(x+1)^((n+1)/2) = (x+1) exposant ((n+1)/2)

Racine carrée :
V(...)      avec ou sans parenthèses selon ce qu'il y a en dessous.
par exemple
V2 = racine de 2
V(x+1) = racine de (x+1)
Vx+1 = (racine de x) + 1

Racine cubique :
³V(...)      meme principe que pour la racine carrée.

racine n-ème:
Si vous voulez vraiment utiliser le symbole "racine" je vous propose
(nV)(...)
mais il est plus facile d'écrire
a^(1/n) pour racine nème de a

Symbole pour si et seulement si
<=>
ou bien
ssi

Plus petit ou égal:
<=
plus grand ou égal:
>=
différent
!=  ou bien  <>

a appartient à B
a€B

petite astuce pour écrire un beau R (de l'ensemble des réels):
écrire ir en majuscule, ce qui donne IR
(merci Mary ;) )


Pour des trucs un peu plus compliqués, je laisse place à votre imagination et à vos propositions, mais voici quand-même quelque petites choses intelligentes que j'ai déjà rencontré...

Pour remplacer le symbole de somme (sigma)
som("ce qu'on met en dessous";"ce qu'on met au dessus";expression)
exemples:
som(i=0;n;i²)
ou pour faire beaucoup plus compliqué
som(0<i<j<k<n;;i+2j-e^(2^(j+k)))

Idem pour les integrales
int(0,pi/2,sin(x)dx)

Idem pour le produit de termes
prod(i=1;n;i) = n!


Pour ce qui est de suites, les parenthèses embrouillent tout. Moi j'opte pour les crochets:
a[1],a[2],a[3],...

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