La "fonction d'Ackerman" $A$ est la fonction de deux entiers naturels définie ainsi :
\begin{align*}
\forall n\in\mathbb N,\quad A(0,n)&= n+1;&\\
\forall m\in\mathbb N,\quad A(m+1,0) &= A(m,1);&\\
\forall (m,n)\in\mathbb N^2,\quad A(m+1,n+1)&= A\left(m,A(m+1,n)\right).&
\end{align*}
-
Calculer $A(0,0)$, $A(0,1)$ et $A(1,0)$.
Corrigé
$A(0,0) = 1$ en appliquant la première règle avec $n=0$.
$A(0,1) = 2$, en appliquant la première règle avec $n=1$.
$A(1,0) = A(0,1) = 2$ en appliquant la deuxième règle avec $m=0$.
-
Calculer $A(m,n)$ pour tout $m\le 3$ et $n\le 5$. Présenter les résultats dans un tableau.
Corrigé
La première ligne de la table est remplie à partir de la première règle
\[\begin{array}{|l||c|c|c|c|c|c|}\hline
m\downarrow,\ n\rightarrow& 0 & 1 & 2 & 3 & 4 & 5 \\ \hline\hline
0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline
1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline
2& 3 & 5 & 7 & 9 & 11 & 13 \\ \hline
3 & 5 & 13 & 29 & 61 & 125 & 253 \\ \hline
\end{array}
\]
-
Émettre des conjectures sur les expressions de $A(1,n)$ et $A(2,n)$ en fonction de $n$ et les démontrer.
Corrigé
Il semble que pour tout $n\in\mathbb N$, $A(1,n) = n+2$.
En effet, pour tout $n\in\mathbb N$:
\[A(1,n) = A(0,n+1) = (n+1) + 1 = n+2.\]
Il semble également que $A(2,n) = 3+2n$ pour tout entier naturel $n$.
Démontrons-le par récurrence :
$A(2,0) = A(1,1) = 3$ et $3+2 \times 0 = 3$, donc la propriété est vérifiée au rang 0.
Si $A(2,n) = 3 + 2n$, alors:
\[\begin{aligned}
A(2,n+1) &= A\left(1,A(2,n)\right)&
\\
&= A\left(1,3+2n\right)&
\\
&= (3+2n) + 2&
\\
&= 3 + 2n + 2&
\\
&= 3 + 2(n+1).&
\end{aligned}\]
La propriété est donc aussi héréditaire, donc vérifiée par récurrence pour tout entier naturel $n$.
-
Démontrer que :
\[\forall n\in\mathbb N,\quad A(3,n) = 2^{n+3} - 3.\]
Corrigé
La propriété est initialisée car $2^{0+3}- 3 = 8 - 3 = 5$, or $A(3,0) = 5$.
Supposons maintenant la propriété vérifiée au rang $n$. Alors :
\[\begin{aligned}
A(3,n+1) &= A\left(2,A(3,n)\right)&
\\
&= A\left(2,2^{n+3}-3\right)&
\\
&= 3 + 2\left(2^{n+3} - 3\right)&
\\
&= 3 + 2\times 2^{n+3} - 2\times 3&
\\
&= 2^{n+3+1} - 3&
\\
&= 2^{(n+1) + 3} - 3.&
\end{aligned}\]
La propriété est donc aussi héréditaire, et par récurrence vraie pour tout entier naturel $n$.