Fonction d'Ackerman et récurrence

[invite10126ba9]

Bonjour à tous,

J'ai un DM à faire avec une fonction d'Ackerman et je suis complètement perdue ! Voici l'énoncé:

La fonction d'Ackerman est une fonction de deux entiers naturels définie ainsi:

A(0,n)= n+1 pour tout entier n appartenant à N
A(m+1,0)= A(m,1) pour tout entier m appartenant à N
A(m+1,n+1)= A(m,A(m+1,n)) pour tous entier m et n appartenant à N

1) Calculer A(0,0), A(0,1) et A(1,0)
2) Calculer A(m,n) pour tout entier m compris entre 0 et 3 et tout entier n compris entre 0 et 5 (à présenter dans un tableau)
3) Emettre des conjoncture sur les expressions de A(1,n) et de A(2,n) en fonction de n et les démontrer.
4) Démontrer que A(3,n)= 2ⁿ⁺³-3 pour tout n supérieur ou égal à 0.

Je suis déjà parvenue à faire la première question mais les 3 dernières me posent problème.

Je remercie d'avance tous ceux qui pourront m'apporter de l'aide.
-----

[Médiat]

Bonjour,

Montrez-nous ce que vous avez fait pour la deuxième question, et nous pourrons vous aider (si vous commencer par écrire vos résultat sous forme d'un tableau, les calcules deviennent très simples).

[invite10126ba9]

Bonjour,

Voici mes réponses à la question 1)

A(0;0)=0+1=1 en utilisant A(0,n)=n+1
A(0;1)=1+1=2 en utilisant aussi A(0,n)=n+1
A(1,0)=A(0,1)=2 en utilisant A(m+1;0)=A(m+1)

Merci pour votre aide

[Médiat]

Quelles difficultés éprouvez-vous pour calculer A(0;2), A(0;3), A(0;4) et A(0;5) ?

Quelles difficultés éprouvez-vous pour calculer A(2, 0), A(3;0) ?

Il vous suffit de remplir le tableau ci-dessous :

m\n
0
1
2
3
4
5

0
1
2





1
2






2







3

[A voir en vidéo sur Futura]

[invite10126ba9]

Et bien mon problème est que je ne sais jamais quelle formule des trois utilisées.

[Médiat]

Pour calculer A(0;2) vous avez la formule A(0;n) = n + 1

[invite10126ba9]

Quand 0 est présent c'est soit la première soit la deuxième suivant sa place d'après ce que j'ai compris. En revanche pour la troisième j'arrive vraiment pas à la comprendre !

[Médiat]

Commencez par compléter le tableau avec ce que vous pouvez calculer facilement !

[invite10126ba9]

Je rencontre un problème à la case A(2;1) voici mon calcul:

A(2;1)= (1+1;0+1) j'utilise A(m+1;n+1)=A(m;A(m+1;n) avec m=1 et n=0

A(2;1)= A(1;A(1+1;0))= A (1;A(2;0))= A(1;3) puisque nous avons déjà calculé A(2;0)=3

A(2;1)= A(1;A(2;0)= A(1;3)= 5

Or c'est ici que se pose mon problème car pour les 2 premières lignes du tableau j'ai trouvé des nombres qui se suivaient (voir ci-dessous) il me semble donc anormal de trouver un 5 à côté d'un 3

m/n	0	1	2	3	4	5
0	1	2	3	4	5	6
1	2	3	4	5	6	7
2	3	5
3	4

Sauriez-vous me dire où est mon erreur ?

[Médiat]

A(2;1) est bien égal à 5. Votre raisonnement pour "croire" que votre raisonnement est faux est anti-mathématique (Cantor disait "je le vois mais je ne le crois pas"), même si vous n'y croyez pas, si vos calculs sont bons, alors le résultat est bon, que vous l'aimiez ou pas.

Par contre votre calcul de A(3;0) est faux.

Construisez tout le tableau avant de faire des conjectures.

[invite10126ba9]

Effectivement j'ai encore un raisonnement trop scolaire... J'ai vu mon erreur pour A(3;0) et j'ai continué la troisième ligne mais à A(2;3) je rencontre un nouveau problème. Voici une partie de mon calcul:

A(2;3)= A(1;A(1+1;2))= A(1;A(2;2))= A(1;7) puisque nous avons déjà calculé A(2;2)= 7

A(2;1)= A(1; A(2;2))= A(1;7)= ?

En effet A(1;7) n'existe pas dans le tableau donc comment trouver le résultat ?

[Médiat]

Oui, mais vous pouvez continuer votre raisonnement :

A(1;7) = A(0;A(1;6)) = A(1;6) + 1
A(1;6) = A(0;A(1;5)) = A(1;5) + 1 = 7 + 1 = 8
A(1;7) = 9

[invite10126ba9]

D'où vient ce +1 ?

[Médiat]

Définition de A(0;n)

[invite10126ba9]

J'ai compris l'astuce pour cette ligne maintenant pour la dernière je suis à nouveau coincée ! Pour A(3;2) j'ai A(2;A(3;1))=A(2;11) donc ici je ne pense pas que l'on puisse réutiliser la formule A(0;n)= n+1 ?

[Médiat]

Pourriez-vous poster votre tableau, là où vous en êtes ...

[invite10126ba9]

m/n	0	1	2	3	4	5
0	1	2	3	4	5	6
1	2	3	4	5	6	7
2	3	5	7	9	11	13
3	5	11

Le voici

[Médiat]

A(3;1) = a(2;a(3;0)) = a(2;5) = 13

[invite10126ba9]

Effectivement j'ai fait une erreur ici mais malheureusement ça ne m'enlève pas mon problème pour A(3;2)

[Médiat]

C'est comme pour les autres :
A(3;2) = A(2;A(3;1)) = A(2;13)
A(2;13) = A(1;A(2;12)) ... à vous de continuer ...

[invite10126ba9]

J'ai terminé le tableau en entier. Pourriez vous me dire si il est juste ?

m/n	0	1	2	3	4	5
0	1	2	3	4	5	6
1	2	3	4	5	6	7
2	3	5	7	9	11	13
3	5	13	15	16	18	21

[Médiat]

Non, dès A(3;2) c'est faux, postez vos calculs ...

[invite10126ba9]

A(3;2)= a(2;a(2+1;1))= a(2;a(3;1))= a(2;13))= a(3;1)=11

a(3;2)= a(2;a(3;1))= a(2;13)

a(2;13)=a(1;a(2;12))= a(2;12)) +1
a(2;12)= a(1;a(2;11)) +1 = 13+1=14
a(2;13) = 14+1=15


a(3;3)= a(2;a(3;2))= a(2;15)= a(3;2)=15
a(3;3)= a(2;a(3;2))= a(2;15)

a(2;15)= a(1;a(2;14))= a(2;14)+1
a(2;14)=a (1;a(2;14))+1= a(1;a(2;13))+1
a(2;13)= 15+1=16

a(3;4)=a(2;a(3;3))= a(2;16)= a(3;3)=16

a(2;16)=a(1;a(2;15))=a(2;15)+1
a(2;15)=a(1;a(2;15)+1=16+1=17
a(2;16)=18

a(3;5)=a(2;a(3;4)=a(2;18)

a(2;18)=a(1;a(2;16))= a(2;16)+1
a(2;16)= a(1;a(2;16)+1=18+1=19
a(2;17)= a(1;a(2;16)+1=19+1=20
a(2;18)=21

[Médiat]

a(3;2)= a(2;a(3;1))= a(2;13) est juste

a(2;13)=a(1;a(2;12))= a(2;12)) +1 est faux (d'où tenez-vous que A(1;n) = n + 1 ?)

[invite10126ba9]

Je sais pas... J'avoue que j'ai du mal à comprendre cette partie des calculs donc j'ai essayé de faire au mieux

[invite10126ba9]

m/n	0	1	2	3	4	5
0	1	2	3	4	5	6
1	2	3	4	5	6	7
2	3	5	7	9	11	13
3	5	13	29	61	125	253

J'ai finalement réussi à finir le tableau. Pourriez vous me dire si cette fois-ci il est juste ?

[Médiat]

Oui, c'est correct.

Il devrait être assez facile de conjecturer les valeurs de A(1;n) et A(2;n) ; pour A(3;n) c'est un peu plus compliqué, mais que se passe-t-il si vous ajoutez 3 à toutes ces valeurs.

[invite10126ba9]

On augmente de 1 ?? C'est surement pas cette réponse mais je vois pas du tout autrement

[invite8351b2a5]

Pour A(1,n) c'est n+1 et A(2,n) c'est 2n+3.