# Exemple 1
def u1(n):
if n==0: return 2
elif n==1: return 1
else: return u1(n-1) + u1(n-2) # très mauvais mais marche pour n petit
[u1(n) for n in range(10)]
C'est suffisant pour reconnaître les nombres de Lucas.
# Evidemment, il ne faut pas faire deux appels récursifs !
def u1(n):
a,b = 2,1
if n==0: return a
elif n==1: return b
else:
for i in range(n-1):
a,b = b,a+b
return b
print [u1(n) for n in range(10)]
print u1(500) # ne marcherait pas avec la première version
# Exemple 2
# Version bête pour vérifier les premiers termes
def u2(n):
if n<2: return 1
elif n==2: return 2
else: return u2(n-1)+u2(n-2)-u2(n-3)
[u2(n) for n in range(10)]
# Facile de deviner, mais on écrit quand même la bonne version
def u2(n):
if n<2: return 1
elif n==2: return 2
else:
a,b,c = 1,1,2
for i in range(n-2):
a,b,c = b,c,c+b-a
return c
print [u2(n) for n in range(20)]
print u2(1000)
# Exemple 3
def u3(n):
if n<2: return 1
else:
return 2*u3(n-1)-u3(n-2)+n-1
[u3(n) for n in range(15)]
Curieusement, cette suite (prise au hasard) est dans l'encyclopédie (avec une définition différente).
# Exemple 4
def u4(n):
if n==0: return 1
else: return sum([u4(i)*u4(n-1-i) for i in range(n)])
[u4(n) for n in range(10)]
On reconnait les nombres de Catalan (presque avec la définition du cours).
# Exemple 5
def u5(n):
if n<2: return 1
else: return u5(n-1) + sum([u5(i)*u5(n-2-i) for i in range(n-1)])
[u5(n) for n in range(10)]
Elle est connue aussi : ce sont les nombres de Motzkin.
C'est une variante de la suite de Fibonacci : on écrit $$ U(x) =\sum_{n\ge 0}u_n x^n = 2+x+\sum_{n\ge 2}(u_{n-1}+u_{n-2})x^n = 2+x+x(U(x)-2)+x^2U(x) $$ d'où $$ (1-x-x^2)U(x)= 2-x,\quad \text{soit}\ U(x)=\frac{2-x}{1-x-x^2}. $$
# Premier test avec sympy
from sympy import *
var('x')
U = (2-x)/(1-x-x**2)
series(U,x,0,10)
Une fois la bonne série obtenue, il faut chercher une formule pour $u_n$. Dans le cas des fractions rationnelles, on décompose en éléments simples au moyen de la méthode apart :
U.apart()
Ça ne donne rien. Il faut lire la documentation de apart et utiliser la bonne option.
apart(U,x,full=True).doit()
a = (1-sqrt(5))/2; b=(1+sqrt(5))/2;a,b
def f(n):
return simplify(a**n+b**n)
[f(n) for n in range(8)]
# La fonction binomial existe déja dans sympy
[binomial(n+3,n) for n in range(9)]
# Pour la coder nous-mêmes, il vaut mieux utiliser la récurrence du triangle de Pascal
def mybin(n,k):
if n<k: return 0
if k==0: return 1
return mybin(n-1,k-1)+mybin(n-1,k)
[mybin(5,i) for i in range(6)]
On connaît le développement $$ \frac{1}{(1-x)^k} = \sum_{n\ge 0}{n+k-1\choose n}x^n. $$
print [binomial(n+4-1,n) for n in range(10)]
series(1/(1-x)**4,x,0,10)
On a cette fois $$ U(x) = 1+x+2x^2+\sum_{n\ge 3}(u_{n-1}+u_{n-2}-u_{n-3})x^n = 1+x+2x^2+x(U(x)-x-1)+x^2(U(x)-1)-x^3U(x)$$ et donc $$ U(x)=\frac1{1-x-x^2+x^3} = \frac1{(1-x)^2(1+x)}. $$
# On teste
U = 1/(1-x-x**2+x**3)
series(U,x,0,10)
# On décompose en éléments simples
apart(U,x)
On a donc $$ U(x)= \frac{1}{4} \frac{1}{1+x} + \frac{1}{4} \frac{1}{1-x} + \frac{1}{2}\frac1{(1-x)^2} $$ de sorte que $$ u_n = \frac{1+(-1)^n}4 +\frac{n+1}2 $$
def f(n): return (2*n+3+(-1)**n)/4
[f(n) for n in range(20)]
On obtient $$U(x) = 1+x +2x(U(x)-1)-x^2U(x) + \frac{x^2}{(1-x)^2}$$ et donc $$U(x) = \frac1{1-x}+\frac{x^2}{(1-x)^4}$$ ce qui donne $$ u_n = 1+{n-2+4-1\choose n-2} = 1+{n+1\choose n-2}= 1+\frac{n(n^2-1)}6. $$
U = 1/(1-x)+x**2/(1-x)**4
series(U,x,0,10)
def f(n): return 1+n*(n*n-1)/6
[f(n) for n in range(10)]
La formule du binôme généralisé s'écrit $$(1+x)^\alpha = \sum_{n\ge 0}{\alpha \choose n}x^n$$ avec $${\alpha \choose n} = \frac{\alpha(\alpha-1)\cdots(\alpha-n+1)}{n!}.$$
def bingen(a,n):
if n==0: return 1
return reduce(lambda x,y:x*y, [Rational(a-i,i+1) for i in range(n)])
[bingen(Rational(1,2),n) for n in range(10)]
series(sqrt(1+x),x,0,9)
Pour l'exemple 4, $$U(x) = 1+\sum_{n\ge 1}\left(\sum_{i=0}^{n-1}u_iu_{n-1-i}\right)x^n = 1 +(u_0u_0)x +(u_0u_1+u_1u_0)x^2+\cdots$$ comparé avec $$U(x)^2 = u_0u_0 + (u_0u_1+u_1u_0)x +\cdots$$ nous apprend que $$ U(x)=1+xU(x)^2 $$ et donc, $U(x)$ est l'une des deux solutions de l'équation du second degré $$ xX^2-X+1=0. $$ Le discriminant est $\Delta = (-1)^2-4x=1-4x$, donc $X = \frac{1\pm \sqrt{1-4x}}{2x}.$ Pour que le développement commence par $1$, il faut prendre le signe $-$, et donc $$ U(x) = \frac{1-\sqrt{1-4x}}{2x}. $$
U = (1-sqrt(1-4*x))/(2*x)
series(U,x,0,10)
Le développement binomial généralisé $$(1-4x)^{\frac12} = \sum_{n\ge 0}{\frac12\choose n}(-4x)^n$$ nous montre alors que $$ u_n = -\frac12(-4)^{n+1}{\frac12\choose n+1} = \ldots = \frac1{n}{2n\choose n-1}=\frac1{n+1}{2n\choose n} $$
[binomial(2*n,n)/(n+1) for n in range(1,9)]
a = Rational(1,2)
[-a*(-4)**(n+1)*bingen(a,n+1) for n in range(1,9)]
Finalement, la récurence de l'exemple 5 se traduit par $$ U(x)=1+x+\sum_{n\ge 2}\left(u_{n-1}+\sum_{i=0}^{n-2}u_iu_{n-i}\right)x^n = 1+x+x(U(x)-1)+x^2U(x)^2, $$ et donc $U(x)$ esr racine de l'équation $x^2X^2+(x-1)X+1=0$. Le discriminant est $\Delta=1-2x-3x^2$, et la solution qui commence par $1+x+\cdots$ est $$ U(x)=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}. $$
U=(1-x-sqrt(1-2*x-3*x**2))/(2*x**2)
series(U,x,0,10).removeO().as_poly().all_coeffs()[::-1]
L'encyclopédie nous apprend que ce sont les nombres de Motzkin. Il n'existe pas de formule simple pour $u_n$. On a par exemple $$ u_n = \frac1{n+1}\sum_{k=0}^{\lceil \frac{n+1}{2}\rceil} {n+1\choose k}{n+1-k\choose k-1} $$
def f(n):
if n<2: return 1
return sum([binomial(n+1,k)*binomial(n+1-k,k-1) for k in range( 1+ ceiling((n+1)/2.) ) ])/(n+1)
[f(n) for n in range(10)]
ceiling(5.8)