Flèches de Knuth

Définition intuitive

Les puissances itérées de Knuth généralisent la notion de l’exponentiation pour pouvoir écrire de plus grand nombres.

La multiplication est une addition itérée. Exemple : $3 \times 4 = \underset{4 \text{ exemplaires de } 3}{\underbrace{3 + 3 + 3 + 3}}$
De même, la puissance est une multiplication itérée. Exemple : $3^4 = \underset{4 \text{ exemplaires de } 3}{\underbrace{3 \times 3 \times 3 \times 3}}$
On définit les puissances itérées de Knuth, en suivant le même principe que les opérations mentionnées précédemment :

• L’opération $\uparrow$ désigne l’exponentiation classique : $3\uparrow 4 = 3 ^4$
• L’opération $\uparrow \uparrow$ est une itération de l’opération $\uparrow$ : $3 \uparrow \uparrow 4 = \underset{4 \text{ exemplaires de } 3}{\underbrace{3 \uparrow 3 \uparrow 3 \uparrow 3}}$
• De même, l’opération $\uparrow \uparrow \uparrow$ est une itération de $\uparrow \uparrow$ : $3 \uparrow \uparrow \uparrow 4 = \underset{4 \text{ exemplaires de } 3}{\underbrace{3 \uparrow \uparrow 3 \uparrow \uparrow 3 \uparrow \uparrow 3}}$
• et ainsi de suite...

Définition formelle

On note $\uparrow$ l’opération classique d’exponentiation : $\forall a, b \in \N^*, a \uparrow b = a ^b$

Cette notation $\uparrow$ se généralise de la manière suivante par récurrence :
Soit $n \in \N^*$, $\forall a, b \in \N^*, a \underset{n+1 \text{ flèches}}{\underbrace{\uparrow \cdots \uparrow}} b$ $= \underset{b \text{ exemplaires de } a}{\underbrace{a \text{ } \underset{n \text{ flèches}}{\underbrace{\uparrow \cdots \uparrow}} \text{ } a \cdots a \text{ } \underset{n \text{ flèches}}{\underbrace{\uparrow \cdots \uparrow}} \text{ } a}}$