# 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)])
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.
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)])
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 :
print ([S(n) for n in range(7,11)])
Ç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.
def v(n):
if n<1: return 1
return 3*v(n-1)-1
print ([v(n) for n in range(7)])
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 :
from sympy import *
var('x')
V = (1-2*x)/((1-x)*(1-3*x))
apart(V)
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 :
print([(3**n+1)//2 for n in range(7)])
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 :
factor(1-2*x-x**2+2*x**3)
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 :
U = (1-x)/((1+x)*(1-2*x))
apart(U)
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 :
series(U,x,0,10)
print [(2**n+2*(-1)**n)/3 for n in range(10)]
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)])
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}$.
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)])
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$).
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)])
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 :
def B(n):
return (-1)**n*Rational(n+1, (2*n+2)**2+1)
print ([B(n) for n in range(12)])
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.
bb = (x+1)/((2*x+2)**2+1)
cc = bb.subs(x,x-1); cc
dd = cc+bb
# Il y a un bug dans simplify, on décompose le calcul
dd.as_numer_denom()
list(map(expand,_))
[factor(_[0]),factor(_[1]-4)]