1. Calcul 

La procédure ci-dessous code une récurrence exprimant le nombre de marches de longueur n en fonction du nombre de marches de longueur n-1. 

>	f:=proc(n,i,j) option remember; if i<0 or j<0 or n<0 then 0 elif n=0 then if i=0 and j=0 then 1 else 0 fi else f(n-1,i-1,j-1)+f(n-1,i,j+1)+f(n-1,i+1,j) fi end:

 

>	a:=proc(n) f(n,0,0) end:

 

>	a(0),a(9),a(21);

 

2. Conjectures sur l'asymptotique 

Le comportement est donné sous la forme 

>	as:=C*n^alpha*rho^n*(1+a/n+b/n^2+O(1/n^3));

 

Le logarithme permet l'accélération de convergence une fois que l'on se débarasse du terme en ln(n) : 

>	lnas:=asympt(simplify(ln(as),symbolic),n);

 

>	map(expand,asympt(subs(n=2*n,lnas)-lnas,n));

 

L'idée est donc de faire de l'accélération de convergence sur la suite 

>	asympt(exp(%/n),n);

 

>	Digits:=40:

 

>	LL:=evalf([seq(exp((ln(a(6*i))-ln(a(3*i)))/i),i=1..30)]);

 

>	accel:=proc(L) local l,k,last; l:=L;last[0]:=l[-1];for k while nops(l)>1 do l:=[seq((2^k*l[2*i]-l[i])/(2^k-1),i=1..iquo(nops(l),2))]; last[k]:=l[-1] od; [seq(last[k],k=1..k-1)] end:

 

>	accel(LL);

 

Vu qu'il y a 3 pas possibles à chaque étape, on peut raisonnablement conjecturer 27^n pour 3n étapes. 

On passe ensuite à α. 

>	LL2:=evalf([seq(ln(a(6*i))-ln(a(3*i))-ln(27)*i,i=1..30)]/ln(2)):

 

>	accel(LL2);

 

On conjecture donc α=-5/2 et on vérifie que le quotient restant semble bien converger vers une constante: 

>	accel(evalf([seq(a(3*i)/27^i/i^(-5/2),i=1..40)]));

 

3. Une récurrence conjecturée et une formule 

>	L:=[seq(a(i),i=0..30)];

 

>	gfun:-listtorec(L,aa(n));

 

>	rec:=map(collect,%[1],aa,factor);

 

>	rsolve(rec,aa(n));

 

4. L'asymptotique qui en découle 

>	eval(%, n=3*n) assuming irem(3*n,3)=0;

 

>	asympt(%,n);

 

>	map(simplify,%);

 

>	asympt(%,n);

 

On retrouve bien 27 et -5/2, et la constante dont on avait 4 décimales correctes : 

>	evalf(sqrt(3/Pi)/4);

 

5. Un polynôme conjecturé 

>	gfun:-seriestoalgeq(series(add(a(3*i)*t^i,i=0..10),t,31),y(t));

 

>	pola:=subs(y(t)=T,%[1]);

 

6. Sa solution 

>	solve(pola,T);

 

>	map(series,[%],t,3) assuming t>0,t<1/10;

 

C'est donc la première solution qui a un sens combinatoire : 

>

B:=%%[1];

 

Vérification sur un peu plus de termes : 

>	series(B,t,7) assuming t>0,t<1/100;

 

>	series(%-add(a(3*i)*t^i,i=0..6),t);

 

7. Sa solution série 

>	toiter:=T-pola/diff(pola,T);

 

>	newt:=proc(N) local sol; if N=1 then 1 else sol:=convert(newt(iquo(N,2)),polynom); series(eval(toiter,T=sol),t,N+1) fi end:

 

>	newt(100);

 

>	series(%-add(a(3*i)*t^i,i=0..100),t,101);

 

8. Une paramétrisation 

>	resultant(numer(t-(u+2)/u^3),T+u*(u+6)/8,u);

 

>	normal(%/pola);

 

C'est notre polynôme, qui définit donc une courbe qui se paramétrise. 

9. Calcul des séries tronquées 

>	Ftronc:=proc(t,x,y,n) local i,j,k; add(add(add(f(k,i,j)*x^i*y^j,i=0..k),j=0..k)*t^k,k=0..n-1) end:

 

>	Fxtronc:=proc(t,x,n) Ftronc(t,x,0,n) end:

 

>	Fytronc:=proc(t,y,n) Ftronc(t,0,y,n) end:

 

>	Fxtronc(t,x,10);

 

10. Un polynôme conjecturé 

>	S:=series(Fxtronc(t,x,80)+O(t^80),t,80):

 

>	gfun:-seriestoalgeq(S,Fx(t),['ogf']);

 

>	Px0:=collect(numer(normal(subs(Fx(t)=T,%[1]))),T,factor);

 

11. Confrontation avec la conjecture de la question 5 

>	subs(t=t^(1/3),x=0,Px0);

 

>	normal(%/pola);

 

Il y a donc bien coïncidence des conjectures. 

12. F(t;x,y) doit être algébrique 

F est conjecturé algébrique en y=0 et par symétrie en x=0 et donc l'équation du noyau permet alors de conjecturer F algébrique. 

13. Vérification de l'équation du noyau 

>	K:=x*y-t*(x+y+x^2*y^2);

 

>	map(expand,series(K*Ftronc(t,x,y,20)-x*y+x*t*Fxtronc(t,x,20)+y*t*Fytronc(t,y,20),t,20));

 

14. La solution série du noyau 

>	solve(K,y);

 

>	map(normal,map(series,[%],t,3)) assuming x>0;

 

>	y0:=%%[2];

 

>	map(normal,series(y0,t,6)) assuming x>0;

 

15. Vérification à précision 20 

>	map(normal,series(x*y0-x*t*Fxtronc(t,x,20)-subs(y=y0,y*t*Fytronc(t,y,20)),t,21)) assuming x>0;

 

16. Existence d'une unique solution série de l'équation (M) 

D'abord s'il y a solution série, son coefficient de vaut 1 : 

>	Gind:=g[0](x)+t*G1(x,t);

 

>	y0s:=map(normal,series(y0,t,4)) assuming x>0;

 

>	x*t*Gind+y0s*t*subs(x=y0s,Gind)-x*y0s;

 

>	series(%,t,4) assuming x>0;

 

Le premier coefficient doit être nul, ce qui entraine . Ensuite, le remplacement de x par dans l'équation permet d'observer que est une série à coefficients polynomiaux. Du coup, l'équation devient 

>	subs(t=x*t,t*G(t,x)/x=Y0(x,t)/x-t*Y0(x,t)*G(t,Y0(x,t))/x^2);

 

En notant le coefficient de dans , l'extraction du coefficient de donne .
Par récurrence cette équation permet alors de déduire que tous les sont des polynômes en x, ce qui permet de les construire de proche en proche et prouve l'existence d'une unique série solution.  

17. Le polynôme de la question 10 admet une unique série solution 

>	gfun:-algeqtoseries(Px0,t,T,6);

 

Ceci montre qu'il en a au plus une. 

>	serH:=%[-1];

 

Ensuite, on peut récrire l'équation sous la forme  

>	T=collect(Px0/coeff(Px0,T,1)-T,T);

 

Tous les coefficients à droite sont réguliers à l'origine : 

>	map(normal@series,op(2,%),t,12);

 

on voit donc qu'on peut itérer cette équation et obtenir (par point fixe) une solution dans Q(x)[[t]]. 

18. Cette solution vérifie (M) 

Des calculs de résultants vont nous permettre de construire un polynôme annulant à la fois et  

>	numer(subs(T=tHx/t,Px0)):

 

s'annule en t*H(t,x) 

>	resultant(K,subs(tHx=y-T,%),y):

 

s'annule en T=y0-t*H(t,x) 

>	pol1:=numer(normal(subs(T=T/x,%))):

 

s'annule en x*y0-x*t*H(t,x) 

>	numer(subs(T=T/t/x,Px0)):

 

s'annule en T=x*t*H(t,x) 

>	pol2:=resultant(subs(x=y,%),K,y):

 

s'annule en T=y0*t*H(t,y0) 

>	normal(pol1/pol2);

 

Il reste à s'assurer de l'identité de ces deux racines a priori distinctes : 

>	gfun:-algeqtoseries(pol1,t,T,4,true);

 

Il n'y a qu'une solution série solution, et c'est bien celle que nous avons : 

>	map(normal,series(x*y0-x*t*serH,t)) assuming x>0;

 

>	map(normal,series(y0*t*subs(x=y0,convert(serH,polynom)),t,5)) assuming x>0;

 

19. Preuve des conjectures sur l'algébricité 

Nous venons de voir que l'unique solution série H  du polynôme conjecturé  est égale à l'unique solution série de l'équation (M). Ceci prouve que annule la série génératrice F(t;x,0). Celle-ci est donc algébrique ce qui entraine par symétrie l'algébricité de F(t,0,y) puis par l'équation du noyau celle de F(t,x,y). Ceci est donc prouvé, sans même exhiber un polynôme annulateur de F.  

20. Preuve de la formule pour les excursions 

Le polynôme trouvé en question 5 est maintenant prouvé. Il suffit donc d'en déduire équation différentielle puis récurrence : 

>	gfun:-algeqtodiffeq(pola,T(t));

 

>	gfun:-diffeqtorec(%,T(t),u(n));

 

>	rsolve(%,u(n));

 

21. Les retours en (0,1) 

Il est facile de conjecturer que la série génératrice est algébrique : 

>	gfun:-listtoalgeq([seq(f(i,0,1),i=0..100)],T(t),['ogf']);

 

>	polb:=collect(subs(T(t)=T,%[1]),T,factor);

 

En étant un peu plus attentif, on regarde les premières valeurs : 

>	seq(f(i,0,1),i=0..20);

 

on les compare à celles de f(i,0,0) : 

>	seq(f(i,0,0),i=0..20);

 

et il est facile de conjecturer Vérification : 

>	seq(f(i,0,1)-f(i+1,0,0)/2,i=0..100);

 

Pour prouver cette identité, on observe que la série génératrice des est le coefficient de dans la sérfie génératrice trivariée. On part de l'équation du noyau : 

>	K*F(t,x,y)-x*y+x*t*F(t,x,0)+y*t*F(t,0,y);

 

>	series(%,y,2);

 

La série génératrice est donc le coefficient de dans 

>	solve(op(1,%),D[3](F)(t,x,0));

 

c'est-à-dire  

>	gf:=coeff(series(%,x,3),x,0);

 

La dérivée par rapport à s'obtient en dérivant le polynôme minimal : 

>	coeff(series(diff(subs(T=F(t,x,0),Px0),x),x,3),x,0);

 

>	solve(%,D[2](F)(t,0,0));

 

>	subs(D[2](F)(t,0,0)=%,gf);

 

Nous avons donc obtenu la relation entre la série génératrice des et celle des qui conclut la preuve.