Solution du TD 1

Exercices sur papier

1. On considère la suite $(u_n)$ définie par la récurrence $$u_n = u_{n-1}+2n-1,\quad u_0=0.$$ a) Calculer $u_n$ pour $n\le 6$.

In [1]:
# Puisqu'on a la machine sous la main, autant l'utiliser pour vérifier nos calculs !
def u(n):
    if n<1: return 0
    else: return u(n-1)+2*n-1
    
print [u(n) for n in range(7)]
[0, 1, 4, 9, 16, 25, 36]

b) Deviner une formule pour $u_n$.

Manifestement, $$u(n) = n^2.$$

c) Prouver la formule par récurrence.

Elle est vraie pour $n=0$. Si on la suppose vraie jusqu'au rang $n-1$, alors, $$ u_n = (n-1)^2 + 2n -1 = n^2-2n+1+2n-1=n^2,$$ elle est donc encore vraie au rang $n$, CQFD.

d) Exprimer $u_n$ comme une somme (sans récurrence) et imaginer un dessin rendant la solution évidente.

Puisque $u_n$ s'obtient à partir de $u_{n-1}$ en lui ajoutant une fonction de $n$ seul, $f(n)=2n-1$, on a $$u_n = u_{n-1}+f(n)=u_{n-2}+f(n-1)+f(n)=\ldots = u_0+f(1)+f(2)+\cdots + f(n) = \sum_{i=1}^n(2i-1)$$ autrement dit, $$u_n=1+3+5+\cdots+(2n-1)$$ est la somme des $n$ premiers nombres impairs.

Pourquoi cette somme vaut-elle $n^2$ ? C'est l'aire d'un carré de côté $n$, qu'on peut découper ainsi :

$$ \begin{matrix} *&*&*&*&*\\ +&+&+&+&*\\ o&o&o&+&*\\ x&x&o&+&*\\ \bullet&x&o&+&* \end{matrix} $$$$ 5^2 = 1+3+5+7+9$$

2. Mêmes questions pour les sommes alternées $$S_n = \sum_{k=1}^n (-1)^{n-k}k^2.$$

a) Calculer $S_n$ pour n≤6.

In [2]:
def S(n):
    return sum([((-1)**(n-k))*k**2 for k in range(1,n+1)])

print [S(n) for n in range(1,7)]
[1, 3, 6, 10, 15, 21]

b) Deviner une formule pour $S_n$.

$$21=3\times 7,\ 15=5\times 3,\ 10=2\times 5,\ 6=2\times 3, \cdots $$

Il semble bien que $S_n=\frac{n(n+1)}{2}$.

On teste sur les cas suivants avant de se lancer :

In [3]:
print [S(n) for n in range(7,11)]
[28, 36, 45, 55]

Ça a l'air bon, alors on y va. On a bien $S_1=1=1(1+1)/2$. Si on suppose la formule vraie jusqu'au rang $n-1$, on a (attention aux signes !) $$ S_n = -S_{n-1} + n^2 = -\frac{(n-1)n}{2}+n^2 = -\frac12 n^2+\frac12 n + n^2 = \frac{n(n+1)}{2},$$ elle est donc encore vraie au rang suivant, est c'est démontré.

d) Exprimer $S_n$ comme une somme (sans récurrence) ? C'est comme ça qu'elle est définie, à la question précédente, on a fait l'inverse : transformer la somme en récurrence.

Imaginer un dessin rendant la solution évidente.

$$ \begin{matrix} *&*&*&*&*\\ & & & &*\\ *&*&*& &*\\ & &*& &*\\ *& &*& &* \end{matrix} \quad=\quad \begin{matrix} *&*&*&*&*\\ &*&*&*&*\\ & &*&*&*\\ & & &*&*\\ & & & &* \end{matrix} $$$$5^2-4^2+3^2-2^2+1^2 = 1+2+3+4+5=\frac{5(5+1)}{2}$$

3. Soit $(v_n)$ la suite définie par la récurrence $$v_n = 3v_{n-1}-1,\quad v_0=1.$$ a) Calculer les 6 premiers termes.

In [4]:
def v(n):
    if n<1: return 1
    return 3*v(n-1)-1

print [v(n) for n in range(7)]
[1, 2, 5, 14, 41, 122, 365]

b) Trouver une expression de la série génératrice $$V(x)=\sum_{n\ge 0}v_n x^n.$$

On a $$ V(x) = v_0 + \sum_{n\ge 1}(3v_{n-1}-1)x^n = 1+ 3x\sum_{n\ge 1}v_{n-1}x^{n-1} -\sum_{n\ge 1}x^n$$ $$ = 1+3xV(x) -\frac{x}{1-x}.$$ Donc, $$(1-3x)V(x) = 1 -\frac{x}{1-x} = \frac{1-2x}{1-x}$$ et $$V(x)=\frac{1-2x}{(1-x)(1-3x)}.$$

c) En déduire la valeur de $v_n$.

On décompose en éléments simples : $$V(x)=\frac{1-2x}{(1-x)(1-3x)} = \frac{a}{1-x} +\frac{b}{1-3x}$$ car le degré du numérateur est inférieur à celui du dénominateur, et ce dernier n'a que des racines simples. En multipliant par $1-x$ et en posant $x=1$, on trouve $a=\frac12$. En multipliant pas $1-3x$ et en posant $x=\frac13$, on trouve $b=\frac12$.

On peut vérifier avec sympy :

In [5]:
from sympy import *
var('x')
Out[5]:
x
In [6]:
V = (1-2*x)/((1-x)*(1-3*x))
apart(V)
Out[6]:
-1/(2*(3*x - 1)) - 1/(2*(x - 1))

On a donc finalement $$V(x)= \frac12\sum_{n\ge 0}x^n +\frac12\sum_{n\ge 0}(3x)^n = \sum_{n\ge 0}\frac{3^n+1}{2} x^n$$ et ainsi, $$v_n=\frac{3^n+1}{2}.$$ Vérifions :

In [7]:
print [(3**n+1)/2 for n in range(7)]
[1, 2, 5, 14, 41, 122, 365]

Exercices sur machine

4. Soit $(u_n)$ la suite définie par $$u_n=2u_{n-1}+u_{n-2}-2u_{n-3},\quad u_0=1,\ u_1=0, u_2=2.$$ a) Trouver une expression de la série génératrice $U(x)$ de $(u_n)$.

Il faut tout de même faire ce calcul sur papier : $$ U(x) = u_0+u_1 x +u_2 x^2 + \sum_{n\ge 3}(2u_{n-1}+u_{n-2}-2u_{n-3})x^n = 1+2x^2 + 2x(U(x)-1-0x) +x^2(U(x)-1) -2x^3U(x)$$ $$= 1-2x+x^2 + (2x+x^2-2x^3)U(x)$$ donc $$(1-2x-x^2+2x^3)U(x) = (1-x)^2$$ La factorisation du membre droit de cette égalité était évidente, mais le polynôme en facteur de $U(x)$ à gauche se factorise aussi :

In [8]:
factor(1-2*x-x**2+2*x**3)
Out[8]:
(x - 1)*(x + 1)*(2*x - 1)

Il nous reste donc, après simplification par $1-x$, $$(1+x)(1-2x)U(x) = (1-x)$$ soit $$U(x)=\frac{1-x}{(1+x)(1-2x)}$$ On calcule la décomposition avec sympy :

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

On a donc (attention aux signes en recopiant !) $$U(x)= \frac13\frac{1}{1-2x}+\frac23\frac{1}{1+x} = \frac13\sum_{n\ge 0}(2x)^n +\frac23\sum_{n\ge 0}(-x)^n$$ d'où $$U(x) = \sum_{n\ge 0}\frac{2^n+(-1)^n2}{3}$$ soit $$u_n = \frac23(2^{n-1}+(-1)^n)$$.

Vérifions :

In [10]:
series(U,x,0,10)
Out[10]:
1 + 2*x**2 + 2*x**3 + 6*x**4 + 10*x**5 + 22*x**6 + 42*x**7 + 86*x**8 + 170*x**9 + O(x**10)
In [11]:
print [(2**n+2*(-1)**n)/3 for n in range(10)]
[1, 0, 2, 2, 6, 10, 22, 42, 86, 170]
In [12]:
def u(n):
    if n==0: return 1
    elif n==1: return 0
    elif n==2: return 2
    else: return 2*u(n-1)+u(n-2)-2*u(n-3)
    
print [u(n) for n in range(10)]
[1, 0, 2, 2, 6, 10, 22, 42, 86, 170]

5. On considère la suite $(q_n)$ définie par $$q_n = \frac{1+q_{n-1}}{q_{n-2}},\quad q_0=a,\ q_1=b.$$ Il n'existe pas de méthode générale pour résoudre ce genre de récurrence.

a) Programmer la suite avec ${\tt sympy}$.

In [13]:
var('a b')
def q(n):
    if n==0: return a
    if n==1: return b
    return simplify((1+q(n-1))/q(n-2))

print [q(n) for n in range(8)]
[a, b, (b + 1)/a, (a + b + 1)/(a*b), (a + 1)/b, a, b, (b + 1)/a]

On voit que la suite est périodique : $u_6=u_0,\ u_7=u_1$. Donc $u_n = u_{n\mod 6}$. Il n'y a rien de plus à dire ...

6. Soit $A_n$ la somme alternéee $$ A_n = \sum_{k=0}^n (-1)^k\frac{(2k+1)^3}{(2k+1)^4+4}.$$ a) Programmer la fonction $\tt A(n)$ avec $\tt sympy$ (utiliser $\tt Rational$).

In [14]:
def A(n):
    return sum([(-1)**k*Rational((2*k+1)**3,(2*k+1)**4+4) for k in range(n+1)])

print [A(n) for n in range(12)]
[1/5, -2/17, 3/37, -4/65, 5/101, -6/145, 7/197, -8/257, 9/325, -10/401, 11/485, -12/577]

On voit que le numérateur doit être $(-1)^n(n+1)$. Pour le dénominateur, si on retranche 1, on voit apparaître $$ 4,16,36,64,100,144, \ldots$$ c'est $$2^2,4^2,6^2,10^2,12^2,\ldots $$ de sorte que $$A_0 = (-1)^0\frac{0+1}{(2(0+1))^2+1},\ A_1 = (-1)^1\frac{1+1}{(2(1+1))^2+1},\ldots$$ et il semble bien que $$A_n = (-1)^n\frac{n+1}{(2n+2)^2+1}.$$

On teste :

In [15]:
def B(n): 
    return (-1)**n*Rational(n+1, (2*n+2)**2+1)

print [B(n) for n in range(12)] 
[1/5, -2/17, 3/37, -4/65, 5/101, -6/145, 7/197, -8/257, 9/325, -10/401, 11/485, -12/577]

Pour prouver la formule, il suffit de vérifier que le terme général de la somme $A_n$ $$a_n = (-1)^n\frac{(2n+1)^3}{(2n+1)^4+4}$$ est bien la différence $B_n-B_{n-1}$ de deux valeurs consécutives de notre expression conjecturale.

In [16]:
bb = (x+1)/((2*x+2)**2+1)
In [17]:
cc = bb.subs(x,x-1); cc
Out[17]:
x/(4*x**2 + 1)
In [18]:
dd = cc+bb
In [19]:
# Il y a un bug dans simplify, on décompose le calcul
dd.as_numer_denom()
Out[19]:
(x*((2*x + 2)**2 + 1) + (x + 1)*(4*x**2 + 1), (4*x**2 + 1)*((2*x + 2)**2 + 1))
In [20]:
map(expand,_)
Out[20]:
[8*x**3 + 12*x**2 + 6*x + 1, 16*x**4 + 32*x**3 + 24*x**2 + 8*x + 5]
In [21]:
[factor(_[0]),factor(_[1]-4)]
Out[21]:
[(2*x + 1)**3, (2*x + 1)**4]
In [ ]: