Mathématiques pour l'informatique 4

TD 2

Pour étudier des récurrences, il est utile de toujours calculer les premiers termes. Dans les exemples suivants, on demande de commencer par calculer quelques termes à la main (sur papier), puis de programmer la récurrence pour vérifier.

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.\]

Pour chaque exemple, calculez les 6 premiers termes sur le papier, puis écrivez une fonction implémentant la récurrence. Vérifiez vos calculs, et itérez le procédé jusqu'à ce que les résultats coincident.

In [1]:
# Exemple avec les tours de Hanoi
# J'ai calculé 1,3,7,15,31,63 ...

def hanoi(n):
    if n == 0: return 0
    else: return 2*hanoi(n-1)+1
    
for n in range(0, 7):
    print hanoi(n),
0 1 3 7 15 31 63

In [2]:
# On peut aussi écrire
hh = [hanoi(n) for n in range(1,7)]
hh
Out[2]:
[1, 3, 7, 15, 31, 63]

Cela permet de sauvegarder les résultats, et aussi de copier le contenu de la liste avec la souris et de lancer une recherche sur oeis.org.

Séries génératrices

Pour chaque exemple, trouvez une équation vérifiée par la série génératrice de la suite, résolvez la, et testez avec sympy. Par exemple, on trouve pour les tours de Hanoi \[ U(x)=0 + \sum_{n\ge 1}(2u_{n-1}+1)x^n = 2xU(x)+\frac{x}{1-x}\] qui donne \[U(x) = \frac{x}{(1-x)(1-2x)}.\]

In [3]:
# Premier test avec sympy
from sympy import *
var('x')
U = x/((1-x)*(1-2*x))
series(U,x,0,8)
Out[3]:
x + 3*x**2 + 7*x**3 + 15*x**4 + 31*x**5 + 63*x**6 + 127*x**7 + O(x**8)

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 [4]:
U.apart()
Out[4]:
-1/(2*x - 1) + 1/(x - 1)

Maintenant, c'est facile, on a deux séries géométriques : \[ U(x)= \frac1{1-2x} -\frac1{1-x}= \sum_{n\ge 0}(2x)^n-\sum_{n\ge 0}x^n =\sum_{n\ge 0}(2^n-1)x^n\] et donc \(u_n=2^n-1\).

Avec des fractions plus compliquées, il faut connaître le développement \[\frac1{(1-x)^k} = \sum_{n\ge 0}{k+n-1 \choose n}x^n.\]

Ecrire une fonction calculant les coefficients binomiaux, et testez vos formules pour les exemples 2 et 3.

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

Les exemples 4 et 5 sont plus compliqués. 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!}.\] Programmez cette formule, et testez avec l'exemple 4.

Pour l'exemple 5, il n'y a rien d'aussi simple. On trouvera une collection de formules sur oeis.org. Programmez-en quelques unes et comparez leur efficacité.

In [7]:
# On peut manipuler des fractions avec sympy si nécessaire
Rational(21,9)
Out[7]:
7/3
In [7]:
 
In []: