fonction récursive

[invite6ebdfb3e]

Bonjour,
J'ai un exercice à faire dans un dm, seulement il me pose quelques difficultés..c'est pourquoi je cherche de l'aide.

Voici l'enoncé

On considère la fonction A, fonction de deux entiers n et m définie de la manière suivante :
A(0, n) = n + 1 pour tout n de IN
A(m + 1, 0) = A(m, 1), pour tout m de IN
A(m + 1, n + 1) = A(m, A(m+1, n)) pour tous m et n de IN.
1. Calculer A(0, 0), A(0,1), A(1,0).
2. a. Calculer A(1 ; n) pour tous n ≤ 5.
b. Emettre une conjecture sur l'expression de A(1, n) et démontrer cette conjecture.
3. a. Calculer A(2, n) pour tous n ≤ 5.
b. Emettre une conjecture sur l'expression de A(2, n) et démontrer cette conjecture.
4. Calculer A(3, n) pour tous n ≤ 5.
b. Démontrer que pour tout n ∈ IN, A(3, n) = 2^(n + 3) – 3.


Mes reponses:
1. A(0,0)=1 A(0,1)=2 A(1,0)=2
2a; A(1,1)=3 A(1,2)=4 A(1,3)=5 A(1,4)=6 A(1,5)=7

b. La je suis bloquée car je sais qu'il faut que j'utilise un raisonnement par recurence avec Pn la proposition "A(1,n)=n+2" mais ensuite je ne sais pas quel calcul faire... :/

Merci d'avance pour votre aide
-----

[Médiat]

Bonsoir,

Appliquez, la définition : A(m + 1, n + 1) = A(m, A(m+1, n))

[PlaneteF]

Bonsoir,

Tu supposes que : A(1, n)=n+2 (hypothèse de récurrence), et tu dois démontrer que : A(1, n+1)=n+3

Tu sais que par définition : A(1, n+1)=A[0, A(1, n)] et là tu enchaînes en utilisant l'hypothèse de récurrence (cf. couleur bleue).


Cordialement


Edit : Croisement avec Médiat.

[invite6ebdfb3e]

d'Accord merci,

Mais du coup le calcule donne ca :

A(m+1,n+1)=A[m,A(m+1,n) ]
A(1,n+1)=A[0,A(1,n)] avec m=0
A(1,n+1)=A(0,n+2)

Mais cela ne nous donne pas A(A,n+1) = n+3 ????

Merci de votre aide

[A voir en vidéo sur Futura]

[invite51d17075]

mais si ,
que vaut A(0,n+2) ? voir l'énoncé.

ps: petite coquille de frappe dans ton mess A(1,n+1) et pas A(A,n+1)

[invite6ebdfb3e]

Finalement j'ai réussit en faisant le lien avec la formule 1 D

[invite6ebdfb3e]

Ensuite pour la question trois a: Je trouve
A(2,0)=2
A(2,1)=5
A(2,2)=7
A(2,3)=9
A(2,4)=11
A(2,5)=13

Ce qui m'a permis dans la question b. de conjecturer que A(2,n)=2n+3
Mais même problème je ne sais comment procéder avec la récurrence

Sachant que on suppose que A(2,n)=2n+3; et qu'on veut démontrer que A(2,n+1)=2n+4... Je ne sais pas comment commencer le calcul!!

Merci de votre aide

[invite6ebdfb3e]

Mais je ne suis pas sure pour A(2,n+1)=2n+4
???

[invite51d17075]

repars de :
A(m + 1, n + 1) = A(m, A(m+1, n))
donc
A(2,n)=A(1+1,n)=?
et untilise ce que tu sais sur A(1,n) ( l'exercice précédent ).

[invite6ebdfb3e]

Oui j'ai réussit mais je retombe sur A(2,n+1)=2n+5
C'est bien cela, mais donc ma supposition est fausse?

Merci de ton aide

[invite51d17075]

Oui j'ai réussit mais je retombe sur A(2,n+1)=2n+5
C'est bien cela, mais donc ma supposition est fausse?

Merci de ton aide

non c'est faux:
déjà que vaut A(1,n) ? pour être sur.

[invite6ebdfb3e]

Pour la question 4:

La a. Je trouve

A(3,0)=5
A(3,1)=13
A(3,2)=29
A(3,3)=61
A(3,4)=125
A(3,5)=253

Mais alors pour la b. je ne sais pas du tout par ou commencé pour demontrer que A(3,n)=2^(n+3)-3...
Faut t'il encore raisonner par récurrence ?

[invite51d17075]

stop,
dejà tu te trompe je crois sur A(1,n)
d'ou erreur sur A(2,n) et encore sur A(3,n) !
A(1,n) = en fonctiion de n ?
A(2,n ) = en fonction de A(2,0) et ensuite en fonction de n. ?

[invite6ebdfb3e]

A(1,n)=n+2
A(2,n)=2n+3
??? Non?

[invite6ebdfb3e]

Je pense que c'est juste... J'ai besoin d'aide pour démontrer la question 4... :/

[invite51d17075]

A(1,n)=n+2
A(2,n)=2n+3
??? Non?

A(2,0)=5 et pas 3 !
et A(2,n)=2n+5

pour A(3,n) , il faut refaire une recurrence tj en partant de
A(m + 1, n + 1) = A(m, A(m+1, n))
en calculant A(3,0)
et chercher
A(3, n+1) sachant A(3,n)= 2^(n + 3) – 3.

[invite6ebdfb3e]

Si si A(2,0)=A(1,1)=3
Oui j'ai reussit, merci beaucoup

[invite51d17075]

Si si A(2,0)=A(1,1)=3
Oui j'ai reussit, merci beaucoup

non
je ne sais pas comment tu as reussi avec A(2,0)=3 ta formule est fausse.
A(2,0) =A(1,A(1,1))=A(1,1)+2=3+2=5

[invite6ebdfb3e]

Non,
A(2,0)=A(1,1) grace à la deuxième formule

[invite51d17075]

oui, oui, pardon,
désolé, j'étais sur 3 discussions en même temps.

[invite6ebdfb3e]

Pas de souci je te remercie pour ton aide