Mathématiques pour l'informatique 4

Corrigé du TD 2

Les exemples

  1. $u_{n} = u_{n-1}+u_{n-2}$ ($n\ge 2$), $u_0=2$, $u_1=1$.
  2. $u_{n} = u_{n-1}+u_{n-2}-u_{n-3}$ ($n\ge 3$), $u_0=1$, $u_1=1$, $u_2=2$.
  3. $u_{n} = 2u_{n-1}-u_{n-2}+n-1$ ($n\ge 2$), $u_0=1$, $u_1=1$.
  4. $$u_{n}=\sum_{i=0}^{n-1}u_iu_{n-1-i},\ \ u_0=1.$$
  5. $$u_{n+2} - u_{n+1} = \sum_{i=0}^n u_i u_{n-i}, \ \ u_0=1,\ u_1=1.$$
In [1]:
# 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)]
Out[1]:
[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]

C'est suffisant pour reconnaître les nombres de Lucas.

In [2]:
# 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
[2, 1, 3, 4, 7, 11, 18, 29, 47, 76]
311759807762174781605301007201736860141952393239819073913168769888623683854510476118474315229371415703127

In [3]:
# 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)]
        
Out[3]:
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
In [4]:
# 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)
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10]
501

In [5]:
# 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)]
Out[5]:
[1, 1, 2, 5, 11, 21, 36, 57, 85, 121, 166, 221, 287, 365, 456]

Curieusement, cette suite (prise au hasard) est dans l'encyclopédie (avec une définition différente).

In [6]:
# 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)]                  
Out[6]:
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]

On reconnait les nombres de Catalan (presque avec la définition du cours).

In [7]:
# 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)]
Out[7]:
[1, 1, 2, 4, 9, 21, 51, 127, 323, 835]

Elle est connue aussi : ce sont les nombres de Motzkin.

Séries génératrices

Exemple 1

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}. $$

In [8]:
# Premier test avec sympy
from sympy import *
var('x')
U = (2-x)/(1-x-x**2)
series(U,x,0,10)
Out[8]:
2 + x + 3*x**2 + 4*x**3 + 7*x**4 + 11*x**5 + 18*x**6 + 29*x**7 + 47*x**8 + 76*x**9 + O(x**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 :

In [9]:
U.apart()
Out[9]:
(x - 2)/(x**2 + x - 1)

Ça ne donne rien. Il faut lire la documentation de apart et utiliser la bonne option.

In [10]:
apart(U,x,full=True).doit()
Out[10]:
-(-1/2 + sqrt(5)/2)/(x - sqrt(5)/2 + 1/2) - (-sqrt(5)/2 - 1/2)/(x + 1/2 + sqrt(5)/2)
Maintenant, c'est facile, on a deux séries géométriques : avec $$ a = \frac{1-\sqrt{5}}{2}\ \text{et}\ b=\frac{1+\sqrt{5}}{2},$$ on a $$ U(x)= \frac{b}{b+x} +\frac{a}{a+x}= \frac{1}{1-ax}+\frac{1}{1-bx} $$ car, comme remarqué en cours, $ab=-1$. Donc, $$ U(x)= \sum_{n\ge 0}(ax)^n+\sum_{n\ge 0}(bx)^n =\sum_{n\ge 0}(a^n+b^n)x^n $$ de sorte que $u_n=a^n+b^n$.
In [11]:
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)]
Out[11]:
[2, 1, 3, 4, 7, 11, 18, 29]
In [12]:
# La fonction binomial existe déja dans sympy

[binomial(n+3,n) for n in range(9)]
Out[12]:
[1, 4, 10, 20, 35, 56, 84, 120, 165]
In [13]:
# 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)]
Out[13]:
[1, 5, 10, 10, 5, 1]

On connaît le développement $$ \frac{1}{(1-x)^k} = \sum_{n\ge 0}{n+k-1\choose n}x^n. $$

In [14]:
print [binomial(n+4-1,n) for n in range(10)]
[1, 4, 10, 20, 35, 56, 84, 120, 165, 220]

In [15]:
series(1/(1-x)**4,x,0,10)
Out[15]:
1 + 4*x + 10*x**2 + 20*x**3 + 35*x**4 + 56*x**5 + 84*x**6 + 120*x**7 + 165*x**8 + 220*x**9 + O(x**10)

Exemple 2

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)}. $$

In [16]:
# On teste
U = 1/(1-x-x**2+x**3)
series(U,x,0,10)
Out[16]:
1 + x + 2*x**2 + 2*x**3 + 3*x**4 + 3*x**5 + 4*x**6 + 4*x**7 + 5*x**8 + 5*x**9 + O(x**10)
In [17]:
# On décompose en éléments simples
apart(U,x)
Out[17]:
1/(4*(x + 1)) - 1/(4*(x - 1)) + 1/(2*(x - 1)**2)

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 $$

In [18]:
def f(n): return (2*n+3+(-1)**n)/4
[f(n) for n in range(20)]
Out[18]:
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10]

Exemple 3

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. $$

In [19]:
U = 1/(1-x)+x**2/(1-x)**4
series(U,x,0,10)
Out[19]:
1 + x + 2*x**2 + 5*x**3 + 11*x**4 + 21*x**5 + 36*x**6 + 57*x**7 + 85*x**8 + 121*x**9 + O(x**10)
In [20]:
def f(n): return 1+n*(n*n-1)/6
[f(n) for n in range(10)]
Out[20]:
[1, 1, 2, 5, 11, 21, 36, 57, 85, 121]

Exemples 4 et 5

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!}.$$

In [20]:
 
In [21]:
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)]
Out[21]:
[1, 1/2, -1/8, 1/16, -5/128, 7/256, -21/1024, 33/2048, -429/32768, 715/65536]
In [22]:
series(sqrt(1+x),x,0,9)
Out[22]:
1 + x/2 - x**2/8 + x**3/16 - 5*x**4/128 + 7*x**5/256 - 21*x**6/1024 + 33*x**7/2048 - 429*x**8/32768 + O(x**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}. $$

In [23]:
U = (1-sqrt(1-4*x))/(2*x)
series(U,x,0,10)
Out[23]:
1 + x + 2*x**2 + 5*x**3 + 14*x**4 + 42*x**5 + 132*x**6 + 429*x**7 + 1430*x**8 + 4862*x**9 + O(x**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} $$

In [24]:
[binomial(2*n,n)/(n+1) for n in range(1,9)]
Out[24]:
[1, 2, 5, 14, 42, 132, 429, 1430]
In [25]:
a = Rational(1,2)
[-a*(-4)**(n+1)*bingen(a,n+1) for n in range(1,9)]
Out[25]:
[1, 2, 5, 14, 42, 132, 429, 1430]

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}. $$

In [26]:
U=(1-x-sqrt(1-2*x-3*x**2))/(2*x**2)
series(U,x,0,10).removeO().as_poly().all_coeffs()[::-1]
Out[26]:
[1, 1, 2, 4, 9, 21, 51, 127, 323, 835]

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} $$

In [27]:
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)
In [28]:
[f(n) for n in range(10)]
Out[28]:
[1, 1, 2, 4, 9, 21, 51, 127, 323, 835]
In [29]:
ceiling(5.8)
Out[29]:
6