Inscription / Connexion Nouveau Sujet
DM fonction d'Ackerman et raisonnement par récurrence
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 à 
A(m+1,0)= A(m,1) pour tout entier m appartenant à
A(m+1,n+1)= A(m,A(m+1,n)) pour tous entier m et n appartenant à
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)= 2n+3-3 pour tout n
0.
Je remercie d'avance tous ceux qui pourront m'apporter de l'aide.
Bonjour,
Merci pour votre réponse ! Je suis parvenue à à peu près comprendre vos réponses c'est donc déjà énorme pour moi. Ensuite pour la question 2) serait il possible de m'indiquer une marche à suivre car je ne sais pas du tout comment commencer.
Prenons l'exemple de .
j'utilise
avec
.
ce qui me donne :
puisque nous savons, nous l'avons calculé, que
et enfin :
j'utilise
avec
.
Tout le tableau ce fait de cette manière.
Je te conseille d'aller voir ici : 
. Ou sur d'autres sites.
Merci beaucoup pour votre aide ! J'avoue que je suis impressionnée par votre capacité à comprendre et réussir un exercice aussi tordu 
J'aimerais juste savoir comment parvenez vous à savoir quelle formule utilisez parmi les 3 ?
Oh pour te parler franchement, ça ne m'est pas aussi facile que tu sembles le croire. Il me faut secouer vigoureusement les neurones pour trouver ne serait-ce qu'un tout petit calcul 
....vigoureusement et pendant pas mal de temps, car comme disait un des plus grand mathématicien de tous les temps Von Neuman :
"Les mathématiques on n'y comprend rien, on s'habitue c'est tout."
Et puis en toute confidence....il y a Google aussi.
Ah c'est donc ça votre secret GOOGLE ! vous m'en direz tant vous n'auriez jamais dû me le faire savoir car jusqu'à présent j'étais vraiment très impressionnée par votre intelligence je pensais communiquer avec un genre de Dieu des maths !
Cool !
Alors si vous êtes un DIEU des maths vous pourriez facilement m'aider à compléter la dernière ligne de mon tableau qui me pose problème !! Voici où j'en suis:
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
Houla tu as déjà bien avancé 
.
Bon pour remplir la troisième ligne, moi je commenserai par dire :
A(0;n)=n+1
A(1;n)=n+2
A(2;n) est un terme d'une suite arithmétique de premier terme 3 et de raison 2 donc A(2;n)=3+2n
Evidemment c'est des conjectures.....mais bon à la limite on peut le démontrer puisqu'il faut le faire à la question suivante.
Ainsi :
A(3;2)=A(2;A(3;1)=A(2;A(2;A(3;0))=A(2;A(2;5)=A(2;13)=3+2
13=3+26=29
etc....
Sinon je vais essayer d'y réfléchir ....mais ça va pas être facile car on reçoit des amis aujourd'hui. Ce soir peut-être.
Oui essaye comme ça, démontres A(1,n)=n+2 et A(2;n)=3+2n par récurrence. Puis utilise cela pour remplir le tableau. Les calculs de A(3;2) A(3;3) A(3;4) et A(3;5) c'est trop pénible.....des pages et des pages de calcul
Bon j'ai enfin terminé le tableau ! Je trouve 61 pour A(3;3) ensuite 125 pour A(3;4) et 253 pour A(3;5) je sais pas quelle technique j'ai utilisé, récurrence ou pas mais en tout cas fini ! Maintenant je me penche sur la troisième question qui s'apparente à un démontage cérébral pour moi mais je baisse pas les bras !!
Bonsoir,
Je suis moi aussi à la question de cette exercice , et je ne comprend pas comment je peux montrer par récurrence pour : A(1,n) = n + 2 ...
Merci ..
@ Kevini
A(1;0)=A(0;1)=2 P0 vraie (0+2)=2 )
Supposons Pn vraie et montrons Pn+1 :
A(1;n+1)=A(0;A(1;n))=A(0;n+2)=n+3=(n+1)+2 donc si Pn vraie alors Pn+1 vraie
j'ai souligné l'utilisation de l'hypothèse de récurrence.
Bien sûr ! Vous êtes pas obligé de tout faire !! Rien qu'un petit coup de pouce ça m'irait très bien !
Ok.
Initialisation :
A(3;0)=5 or 5=20+3-3 en effet 20+3-3=23-3=8-3=5
P0 est vraie.
Hérédité :
démontrons que si Pn est vraie alors Pn+1 est vraie.
A(3;n+1)=A(2;A(3;n))
or A(3;n)=2n+3-3 ( hypothèse de récurrence )
donc
A(3;n+1)=A(2;2n+3-3)
mais d'après la question 3)
A(2;2n+3-3)=3+2(2n+3)-3)
en développant
3+2(2n+3-3)=3+2n+4-6=2(n+1)+3-3
conclusion : A(3;n+1)=2(n+1)+3-3 cad si Pn est vraie Pn+1 aussi.
Bonsoir à tous,
Simple incompréhension de ma part, désolé de couper le fil
Si on suit la formule : A(m+1, n+1), pourquoi A(2,2) donne 7 et pas 6 ?
Merci d'avance
Toujours pour la question 3 ...
Si je suis ton raisonnement :
A(2;0)=A(1;1)=3 P0 vraie (1+1)=3 )
Supposons Pn vraie et montrons Pn+1 :
A(2;n+1)=A(1;A(2;n))=A(1;2n+1)=2n+3
donc si Pn vraie alors Pn+1 vraie
Faut-il procéder ainsi ?
@ Mrlconnu
A(2;2)=A(1;A(2;1))=A(1;A(1;A(2;0))=A(1;A(1;3))=A(1;A(0;A(1;2))=A(1;A(0;4))=A(1;5)=7 oufff
Encore une fois MisterJack je suis impressionnée !! Merci mille fois pour votre aide ! Bonne continuation à vous
Désolé,
Mais je ne comprend pas pourquoi on ne trouve pas 2n+1 + 3 ....
J'ai vraiement pas compris pour A(2,n) ...
@ Mrlconnu
Merci, je comprends mieux
Y a-t il par contre un raccourcis ^^ je vois sur wikipedia qu'il y a une formule mais il faut pouvoir la démontrer avant de l'utiliser ^^
@ Kevini
Supposons Pn vraie et montrons Pn+1 :
A(2;n+1)=A(1;A(2;n))=A(1;2n+1)=2n+3
donc si Pn vraie alors Pn+1 vraie
Il y a une erreur dans ce que tu as écrit, en fait il faut écrire :
A(2;n)=3+2n c'est l'hypothèse de récurrence.
Ensuite :
A(1;2n+3)=(2n+3)+2 démontrer précédemment ( A(1;n)=n+2 )
Conclusion :
A(2;n+1)=(2n+3)+2=2n+5=2(n+1)+3 Pn+1 est vraie
@ Mrlconnu
Merci, je comprends mieux
Y a-t il par contre un raccourcis ^^ je vois sur wikipedia qu'il y a une formule mais il faut pouvoir la démontrer avant de l'utiliser ^^
effectivement.
C'est vrai que les calculs sont vraiment pénibles. Regardes mon post de 11.35 et les deux suivants.
@MisterJack
Merci beaucoup, j'ai enfin compris .. Je me disais bien que ça aller pas, franchement merci !
Le 3 me poser problème depuis quelques jours ..
Annuler
connectez vous