Semaine 2 - Récurrence

a. $p \choose k = \frac{p!}{k!(p-k)!}$ Cette fraction est un nombre entier. Or $p$ divise évidement $p!$ sans diviser ni $k!$ car $0 \lt k \lt p$ ni $(p-k)!$ car $0 \lt p-k \lt p$, et $p$ étant premier, il ne divise aucune factorielle d'un nombre strictement inférieur à lui même. Ainsi, $p$ divise le numérateur et pas le dénominateur, donc $p$ divise l'entier $p \choose k$

b. En développant $(a_1 + a_2 + ... +a_n)^p$, on verra apparaître des termes $a^p$ et les autres termes auront un coefficient en $p \choose k$ avec $k \neq 0$ et $k \neq p$ (il s'agit des cas où le coefficient vaut 1, c'est à dire ceux en $a^p$), or tous ces termes sont divisibles par $p$. Bref, modulo $p$, on retrouve l'égalité cherchée.

c. En décomposant $a$ comme $a = 1+1+1...$, avec $1^p = 1$, on en déduit immédiatement : $a^p \equiv a [p]$, il s'agit du petit théorême de Fermat.

Pour la a) on peut voir que $p \choose k = \frac{p}{k} {{p-1} \choose {k - 1}}$ ...

On veut montrer par récurrence sur $k \in \mathbb{N}$, avec $n = 2^k$ et des réels strictement positifs $a_1,...a_n$ que : $\frac{a_1+....+a_n}{n} \geq \rootn{a_1 \cdots a_n\right}}$

Initialisation : $k = 0$
$\forall a \in \mathbb{R}_{+}^{*}, a \geq a$
Ca va, pas trop dur à suivre ?

Initialisation : $k = 1$
Je ne suis pas sure que mon initialisation précédente suffise, alors je mets celle-ci aussi car elle est facile et donne pleins de conditions équivalentes intéressantes. Pour $a$ et $b$ réels strictement positifs, on a : $(a-b)^2 \geq 0$ ce qui équivaut successivement, sans trop détailler, à :
$a^2 + b^2 \geq 2ab \Leftrightarrow a^2 + b^2 + 2ab \geq 4ab \Leftrightarrow (a+b)^2 \geq 4ab \Leftrightarrow a+b \geq 2\sqrt{ab} \Leftrightarrow \frac{a+b}{2} \geq \sqrt{ab}$
La dernière inégalité est celle que l'on cherche à généraliser.

Récurrence
Supposons que pour tout $k \in \mathbb{N}$ l'égalité soit vraie. On a donc, pour tout suites de réels strictement positifs $a_n$ et $b_n$ :
$\frac{a_1 +...+a_n}{2^k} \geq \root{2^k}{a_1...a_n}$ et $\frac{b_1 +...+b_n}{2^k} \geq \root{2^k}{b_1...b_n}$
Essayons de "regrouper" ces inégalités pour démontrer ces inégalités pour $n = 2^{k+1}$. En additionnant membre à membre, puis en divisant par 2, il vient :
$\frac{a_1+b_1+...+a_n+b_n}{2^{k+1}} \geq \frac{\root{2^k}{a_1...a_n} + \root{2^k}{b_1...b_n}}{2}$
A gauche, c'est bon. Si on montre que le membre de droite est supérieur à $\root{2^{k+1}}{a_1 b_1 ... a_n b_n}}$, alors par transitivité de la relation d'ordre, l'égalité sera démontrée pour $n = 2^{k+1}$. Comparons donc ces deux membres. La condition $\frac{\root{2^k}{a_1...a_n} + \root{2^k}{b_1...b_n}}{2} \geq \root{2^{k+1}}{a_1 b_1 ... a_n b_n}}$ équivaut, en élevant au carré de chaque côté, à:
$\frac{\root{2^{k-1}}{a_1...a_n} + \root{2^{k-1}}{b_1...b_n} + 2 \root{2^k}{a_1 b_1 ... a_n b_n}}{4} \geq \root{2^{k}}{a_1 b_1 ... a_n b_n}}$
Puis en multipliant par 4 et en arrangeant, cela équivaut à :
$\root{2^{k-1}}{a_1...a_n} + \root{2^{k-1}}{b_1...b_n} \geq 2 \root{2^{k}}{a_1 b_1 ... a_n b_n}}$
Qui se regroupe et se factorise simplement pour obtenir la condition équivalente :
$(\root{2^k}{a_1 ... a_n} - \root{2^k}{b_1 ... b_n})^2 \geq 0$
Qui est évidement toujours vraie. L'inégalité est donc démontrée pour $n = 2^{k+1}$ et donc, par récurrence, pour tout entier $k$.

Puisque l'on sait que l'égalité est vraie pour les valeurs de n de la forme $2^k, k \in \mathbb{N}$, et qu'on peut trouver de telle valeurs aussi grandes que l'on veut, il suffit de montrer que si la propriétés est vraie au rang n, elle l'est forcément au rang n-1 (s'il est positif), en fixant la valeur de $a_n$

Pour une valeur N $\in \mathbb{N}^*$ fixée.
Initialisation:
On pose $n_0 = 2^{E[log_2(N)] + 1$ ainsi $n_0$ est de la forme $2^k, k \in \mathbb{N}$ et N < $n_0$.
On a donc:
$\frac{\sum_{k=1}^{n_0} a_k }{n_0} \geq \root{n_0}{\prod_{k=1}^{n_0} a_k}$

Hérédité:
On remarque que
$\frac{\sum_{k=1}^n a_k }{n} = \frac{\sum_{k=1}^{n-1} a_k }{n - 1}$
<=>
$\frac{a_n}n + \frac{\sum_{k=1}^{n - 1} a_k }{n} = \frac{\sum_{k=1}^{n-1} a_k }{n - 1}$
<=> (on retire $a_n$ de la somme)
$\frac{a_n}n = \frac{\sum_{k=1}^{n-1} a_k }{n - 1} - \frac{\sum_{k=1}^{n - 1} a_k }{n} = \sum_{k=1}^{n - 1} a_k \frac{1}{n-1} - \frac{1}{n}$
<=>
$\frac{a_n}n = \frac{n - (n - 1)}{(n-1)n}\sum_{k=1}^{n - 1} a_k = \frac{1}{(n-1)n}\sum_{k=1}^{n - 1} a_k $
<=>
$a_n = \frac{\sum_{k=1}^{n - 1} a_k }{n-1}$ (simplification par n > 0)

Supposons donc $\frac{\sum_{k=1}^{n - 1} a_k }{n-1} \geq \rootn{\prod_{k=1}^n a_k} $ en prenant $a_n = \frac{\sum_{k=1}^{n - 1} a_k }{n-1}$

On a ainsi:
$\frac{\sum_{k=1}^{n-1} a_k }{n - 1} \geq \rootn{\prod_{k=1}^n a_k} $
Ce qu'on peut aussi écrire:
$a_n \geq \rootn{\prod_{k=1}^n a_k} $
Donc: $(a_n)^n \geq \prod_{k=1}^n a_k $
Puis en simplifiant par $a_n$ ( > 0): $(a_n)^{n-1} \geq \prod_{k=1}^{n-1} a_k $
Soit finalement: $a_n \geq \root{n-1}{\prod_{k=1}^{n-1} a_k}$ Ce qui est bien:

$\frac{\sum_{k=1}^{n - 1} a_k }{n-1} \geq \root{n-1}{\prod_{k=1}^{n-1} a_k}$ (qui est l'inégalité au rang n-1)

Pour n > 1, on a donc:
$\frac{\sum_{k=1}^{n} a_k }{n} \geq \root{n}{\prod_{k=1}^{n} a_k}$ =>$\frac{\sum_{k=1}^{n - 1} a_k }{n-1} \geq \root{n-1}{\prod_{k=1}^{n-1} a_k}$

Conclusion
Par récurrence, on en déduit que pour tout n, tel que $1 \leq n \leq n_0$, $\frac{\sum_{k=1}^{n} a_k }{n} \geq \root{n}{\prod_{k=1}^{n} a_k}$
Or $1 \leq N \leq n_0$ donc $\frac{\sum_{k=1}^{N} a_k }{N} \geq \root{N}{\prod_{k=1}^{N} a_k}$