Chapitre 25  Des calculs de différentes sommes

25.1  La fonction sum de Xcas

Cette fonction permet de calculer :

• la somme d’une liste ou d’une séquence
  sum(n$(n=1..5))=sum(n$(n=5..1))=15,
• une somme ayant une primitive discréte. Par exemple
  sum(n,n=1..5)=15 mais sum(n,n=5..1)=-9=-sum(n,n=2..4) et
  sum(n,n)=(n^2-n)/2=F(n) qui est la primitive discréte de n (sum(n,n=1..5)=F(5+1)-F(1)),
• d’autres sommes en particulier de sommes avec un pas (quand il y a un pas le pas est le 5ième argument et il n’y a pas de différence entre sum(xpr,n,a,b,2)=sum(xpr,n,b,a,2). Par exemple
  sum(n,n,1,5,2)=sum(n,n,5,1,2)=sum(n,n,1,5,-2)=sum(n,n,5,1,-2)=9

Voici quelques exercices...

25.2  Calcul de ∑_k=1ⁿk^p pour p=1,2,3

25.2.1  Calcul de s₁(n)=∑_k=1ⁿk)

On a :
2*s₁=∑_k=1ⁿk)+∑_k=1ⁿn+1−k)=∑_k=1ⁿn+1)=n(n+1)
Donc :

On peut aussi remarquer que :
p(p+1)/2−(p−1)p/2=p
On dit que le polynôme x(x−1)/2 est la primitive discrète du polynôme x On a donc :
2s₁=∑_p=1ⁿ2p=∑_p=1ⁿ(p(p+1)−(p−1)p)=n(n+1)
Avec Xcas, on tape :
sum(k,k=1..n)
On obtient :
(n*(n+1))/2 Remarque
On peut en déduire le calcul de s=∑_k=1ⁿ(2k−1)).
On a en effet :
s=2∑_k=1ⁿk−n=n*(n+1)−n=n²
On aurait aussi pu remarquer que :
2p−1=(p+1)(p−1)−p(p−2)
Donc que la primitive discète du polynôme 2x−1 est le polynôme x(x−2).
On a donc :
s=∑_p=1ⁿ2p−1=∑_p=1ⁿ(p²−(p−1)²)=n²
Avec Xcas, on tape :
normal(sum(2k-1,k=1..n))
On obtient :
n^2

25.2.2  Calcul de s₂(n)=∑_k=1ⁿk²

On a :
1³=1
2³=1³+3*1²+3*1+1
....
k³=(k−1)³+3*(k−1)²+3*(k−1)+1
(k+1)²=k³+3*k²+3*k+1
....
n³=(n−1)³+3*(n−1)²+3*(n−1)+1
(n+1)³=n³+3*n²+3*n+1
En sommant tous les termes :
(n+1)³=3*∑_k=1ⁿk²+3∑_k=1ⁿk+n=3s₂+3n(n+1)/2+n+1
Donc :
3s₂(n)=(n+1)((n+1)²−3n/2−n−1)=(n+1)(2n²+n)/2

On peut aussi remarquer que :
p(p+1)*(2p+1)/6−(p−1)*p*(2p−1)/6=p²
Donc que la primitive discète du polynôme x² est le polynôme x(x−1)(2x−1)/6.
On a donc :
6s₂=∑_p=1ⁿ6p²=∑_p=1ⁿ(p(p+1)(2p+1)−(p−1)p(2p−1))=n(n+1)(2*n+1)
Avec Xcas, on tape :
factor(sum(k^2,k=1..n))
On obtient :
n*(n+1)*(2*n+1)/6

25.2.3  Calcul de s₃(n)=∑_k=1ⁿk³

On a :
1⁴=1
2⁴=1⁴+4*1³+6*1²+4+1
....
k⁴=(k−1)⁴+4*(k−1)³+6*(k−1)²+4*(k−1)+1
(k+1)⁴=k⁴+4*k³+6*k²+4*k+1
....
(n+1)⁴=n⁴+4*n³+6n²+4*n+1
Donc :
(n+1)⁴=n⁴+4s₃(n)+6s₂(n)+4s₁(n)+n Donc : 4s₃(n)= (n+1)⁴−n*(n+1)*(2*n+1)−2n(n+1)−n−1=(n+1)((n+1)³−n(2*n+1)−2n−1)
4s₃(n)=(n+1)²((n+1)²−(2*n+1))=(n+1)²n²

On peut aussi remarquer que :
p²*(p+1)²/4−(p−1)²*p²/4=p³
Donc la primitive discète du polynôme x³ est le polynôme (x−1)²x²/4.
On a donc :
4s₃=∑_p=1ⁿ4p³=∑_p=1ⁿ(p²(p+1)²−(p−1)²p²)=n²(n+1)²
Avec Xcas, on tape :
factor(sum(k^3,k=1..n))
On obtient :
(n^2*(n+1)^2)/4

25.3  Primitive discrète d’un polynôme

25.3.1  Comment trouver la primitive discrète d’un polynôme

Soit P un polynôme de degré d.
On veut calculer pour tout entier n ∈ ℕ les sommes : ∑_k=0ⁿP(k)
On cherche donc une primitive discrète de P c’est à dire une fonction f telle qu’on ait pour tout x ∈ ℝ f(x+1)−f(x)=P(x).
Cela entraine que pour tout entier n ∈ ℕ on a :
f(n+1)−f(0)=∑_k=pⁿP(k).
Donc pour tout entier n ∈ ℕ on doit avoir f(n+1)−f(n)=P(n) On cherche si P a comme primitive discrète un polynôme Q. Si c’est le cas le polynôme Q doit vérifier : Q(x+1)−Q(x)=P(x) avec P un polynôme de degré d donc Q est défini à une constante près et est de degré d+1. Donc Q est entièrement défini par d+2 valeurs qui sont par exemple :
Q(0)=0=q₀ Q(1)=P(0)=q₁
Q(2)=P(0)+P(1)=q₂
Q(3)=P(0)+P(1)+P(2)=q₃
.....
Q(d+1)=P(0)+P(1)+...+P(d)=q_d+1
On calcule q₀,q₁...,q_d+1 et on définit Q comme étant le polynôme d’interpolation de Lagrange des points (k,p_k) pour k=0..d+1.
Soit R le polynôme définit par R(x)=Q(x+1)−Q(x).
Puisque Q est de degré d+1, on en déduit que R est de degré d.
Comme Q(k+1)−Q(k)=P(k) pour k=0..d, on a :
R(k)=P(k) pour k=0..d.
R et P ont même degré d et ils sont égaux en d+1 valeurs donc :
pour tout x ∈ ℝ on a P(x)=R(x)=Q(x+1)−Q(x).
Donc Q est bien une primitive discrète de P.

25.3.2  Reprenons les exemples précédents

Cherchons la primitive discrète de P(x)=x
La primitive discrète de P(x)=x est égale au polynôme de d’interpolation de Lagrange des points :
(0,0), (1,0), (2,1).
On tape :
factor(lagrange([0,1,2],[0,0,1]))
On obtient :
(x*(x-1))/2x
Cherchons la primitive discrète de P(x)=2*x−1
La primitive discrète de P(x)=x² est égale au polynôme de d’interpolation de Lagrange des points :
(0,0), (1,−1), (2,0).
On tape :
factor(lagrange([0,1,2],[0,-1,0]))
On obtient :
x*(x-2)
Cherchons la primitive discrète de P(x)=x².
La primitive discrète de P(x)=x² est égale au polynôme de d’interpolation de Lagrange des points :
(0,0), (1,0), (2,1), (3,5).
On tape :
factor(lagrange([0,1,2,3],[0,0,1,5]))
On obtient :
(x*(x-1)*(2*x-1))/6
Cherchons la primitive discrète de P(x)=x³.
La primitive discrète de P(x)=x³ est égale au polynôme de d’interpolation de Lagrange des points :
(0,0), (1,0), (2,1), (3,9), (4,36).
On tape :
factor(lagrange([0,1,2,3,4],[0,0,1,9,36]))
On obtient :
(x^2*(x-1)^2)/4 Cherchons la primitive discrète de P(x)=x⁴.
La primitive discrète de P(x)=x⁴ est égale au polynôme de d’interpolation de Lagrange des points :
(0,0), (1,0), (2,1), (3,17), (4,98), (5,354).
On tape :
factor(lagrange([0,1,2,3,4,5],[0,0,1,17,98,354]))
On obtient :
(x*(x-1)*(2*x-1)*(3*x^2-3*x-1))/30
On en déduit le calcul de s₄(n)=∑_k=1ⁿk⁴ :
On tape :
factor(subst((x*(x-1)*(2*x-1)*(3*x^2-3*x-1))/30,x=n+1))
On obtient :
(n*(n+1)*(2*n+1)*(3*n^2+3*n-1))/30
s₄(n)=n*(n+1)*(2*n+1)*(3*n²+3*n−1)/30 Ou on tape :
factor(sum(k^4,k=1..n))
On obtient :
(n*(n+1)*(2*n+1)*(3*n^2+3*n-1))/30

25.3.3  Exercice

Calculer ∑_k=4¹⁰k²+2*k−1 et ∑_k=4+√2^10+√2k²+2*k−1
Cherchons la primitive discrète de P(x)=x²+2x−1.
La primitive discrète de P(x)=x²+2x−1 est égale au polynôme de d’interpolation de Lagrange des points :
(0,0), (1,−1), (2,1), (3,8).
On tape :
factor(lagrange([0,1,2,3],[0,-1,1,8]))
On obtient :
(x*(2*x^2+3*x-11))/6
On tape :
f(x):=(x*(2*x^2+3*x-11))/6
Ou on tape directement pour définir f :
f:=unapply(factor(lagrange([0,1,2,3],[0,-1,1,8])),x)
On tape :
f(11)-f(4)
On obtient :
462
On vérifie :
On tape :
sum(k^2+2*k-1,k=4..10)
On obtient :
462
On tape :
normal(f(11+sqrt(2))-f(4+sqrt(2)))
On obtient :
112*sqrt(2)+476
On vérifie :
On tape :
normal(sum(k^2+2*k-1,k=4+sqrt(2)..10+sqrt(2)))
On obtient :
112*sqrt(2)+476

25.4  Calcul de ∑_k=0ⁿk^pcomb(n,k) pour p=0,1,2,3

25.4.1  Calcul de s₀(n)=∑_k=0ⁿcomb(n,k)

On sait que :
(a+b)ⁿ=∑_k=0ⁿcomb(n,k)a^kb^n−k
donc
s₀(n)=∑_k=0ⁿcomb(n,k)=(1+1)ⁿ=2ⁿ
Donc :

Avec Xcas, on tape :
sum(comb(n,k),k=0..n)
On obtient :
2^n

25.4.2  Calcul de s₁(n)=∑_k=0ⁿk*comb(n,k)

On sait que :
comb(n,k)=n!/k!(n−k)!
Donc :
k*comb(n,k)=n*comb(n−1,k−1)
On a :
s₁(n)=∑_k=0ⁿk*comb(n,k)=∑_k=1ⁿk*comb(n,k)=
n*∑_k=1ⁿcomb(n−1,k−1)=n*∑_k=0ⁿ⁻¹comb(n−1,k)=n*2ⁿ⁻¹
Donc :

Avec Xcas, on tape :
sum(k*comb(n,k),k=0..n)
On obtient :
n*2^(n-1)

25.4.3  Calcul de s₂(n)=∑_k=0ⁿk²*comb(n,k)

On sait que :
comb(n,k)=n!/k!(n−k)! et
∑_k=0ⁿk*comb(n,k)=n*2ⁿ⁻¹
Donc :
k²*comb(n,k)=n*k*comb(n−1,k−1) On a :
s₂(n)=∑_k=0ⁿk²*comb(n,k)=∑_k=1ⁿk²*comb(n,k)=
n*∑_k=1ⁿk*comb(n−1,k−1)=n*∑_k=0ⁿ⁻¹(k+1)*comb(n−1,k)=
n*∑_k=0ⁿ⁻¹k*comb(n−1,k)+n*∑_k=0ⁿ⁻¹comb(n−1,k)=
n*(n−1)*2ⁿ⁻²+n*2ⁿ⁻¹=n(n+1)2ⁿ⁻²=n(s₍n−1)+s₀(n−1))
Donc :

Avec Xcas, on tape :
s2:=sum(k^2*comb(n,k),k=0..n)
factor(subst(s2,2^(n-1),2*2^(n-2))) On obtient :
n*(n+1)*2^(n-2)

25.4.4  Calcul de ∑_k=0ⁿk³*comb(n,k)

On sait que :
comb(n,k)=n!/k!(n−k)! et
∑_k=0ⁿk²*comb(n,k)=n(n+1)2ⁿ⁻²
Donc :
s₃(n)=k³*comb(n,k)=n*k²*comb(n−1,k−1) On a :
∑_k=0ⁿk³*comb(n,k)=∑_k=1ⁿk³*comb(n,k)=
n*∑_k=1ⁿk²*comb(n−1,k−1)=n*∑_k=0ⁿ⁻¹(k+1)²*comb(n−1,k)=
n(s₂(n−1)+2*s₁(n−1)+s₀(n−1))=
n(n(n−1)*2ⁿ⁻³+2(n−1)2ⁿ⁻²+2ⁿ⁻¹)=n(n(n−1)+4(n−1)+4)2ⁿ⁻³=n²(n+3)2ⁿ⁻³
Donc :

Avec Xcas, on tape :
s3:=sum(k^3*comb(n,k),k=0..n)
factor(subst(subst(s3,2^(n-2),2^(n-3)*2),2^(n-1),2^(n-3)*4))
On obtient :
n^2*(n+3)*2^(n-3)

25.5  Calcul de ∑_k=1ⁿ1/f(k)

25.5.1  Calcul de ∑_k=1ⁿ1/k(k+1)

On remarque que :
1/k(k+1)=1/k−1/k+1
Donc que :
s=∑_k=1ⁿ1/k(k+1)=∑_k=1ⁿ1/k−1/k+1=1−1/n+1=n/n+1
Avec Xcas, on tape :
normal(sum(1/(k*(k+1)),k=1..n))
On obtient :
n/(n+1)

25.5.2  Calcul de s=∑_k=1ⁿ1/(2k−1)(2k+1)

On remarque que :
2/(2k−1)(2k+1)=1/2k−1−1/2k+1
Donc que :
2s=∑_k=1ⁿ1/(2k−1)(2k+1)=∑_k=1ⁿ1/2k−1−1/2k+1=1−1/2n+1=2n/2n+1
Donc :

Avec Xcas, on tape :
normal(sum(1/((2k-1)*(2k+1)),k=1..n))
On obtient :
n/(2n+1)

25.5.3  Calcul de ∑_k=1ⁿ1/k(k+2)

On remarque que :
2/(k)(k+2)=1/k−1/k+2
Donc que :
2s=∑_k=1ⁿ1/k(k+2)=∑_k=1ⁿ1/k−1/k+2=∑_p=1ⁿ1/p−∑_p=3ⁿ⁺²1/p=1+1/2−1/n+1−1/n+2=3*n²+5*n/2*n²+6*n+4
Donc :

Avec Xcas, on tape :
normal(sum(1/(k*(k+2)),k=1..n))
On obtient :
(3*n^2+5*n)/(4*n^2+12*n+8)

25.5.4  Calcul de ∑_k=1ⁿ1/k(k+1)(k+2)

On tape : partfrac(1/(k*(k+1)*(k+2)),k)
On obtient :
1/(k*2)-1/(k+1)+1/((k+2)*2)
Donc :
2*s=∑_k=1ⁿ1/k−1/(k+1)−(1/(k+1)−1/(k+2))=
∑_p=1ⁿ1/p−1/(p+1)−∑_k=2ⁿ⁺¹1/p−1/(p+1)=
2s=1−1/2−1/n+1+1/(n+2)=(n²+3*n)/(2*n²+6*n+4) Donc :

Avec Xcas, on tape :
normal(sum(1/(k*(k+2)),k=1..n))
On obtient :
(n^2+3*n)/(4*n^2+12*n+8))

25.6  Des calculs de sommes avec un programme

On veut savoir si la convergence d’une série est lente ou rapide, par exemple savoir combien il faut de termes pour que ∑_k=1ⁿ1/k>10.
On peut taper :
sum(1./n,n=1..20000)
On obtient :
0.1048072821722932757281444e2
ou faire un calcul exact plus long :
s:=sum(1/n,n=1..20000)
On obtient :
Integer_too_large_for_display/Integer_too_large_for_display On tape alors :
evalf(s)
On obtient :
0.1048072821722932757281444e2 On veut voir l’incidence qu’il y a sur la précision et sur le temmps d’exécution selon que l’on commence à faire la somme par le plus petit indice ou par le plus grand indice ou faire la somme avec une procédure récursive.
On suppose a≤ b sinon on échange a et b.

//som1 fait la somme de a jusque b 
som1(u,a,b):={
local k,c,s;
si b<a alors c:=b;b:=a;a:=c;fsi;
s:=0;
pour k de a jusque b faire
s:=s+u(k);
fpour;
return s;
}
:;
//som2 fait la somme de b jusque a
som2(u,a,b):={
local k,c,s;
si b<a alors c:=b;b:=a;a:=c;fsi;
s:=0;
pour k de b jusque a pas -1 faire
s:=s+u(k);
fpour;
return s;
}
:;
//som3 fait la somme recusivement en partageant en 2
som3(u,a,b):={
local k,c,s;
si a>b alors return som3(u,b,a); fsi;
si a==b alors return u(a); fsi;
si b==a+1 alors return u(a)+u(b); fsi; 
c:=floor((a+b)/2);
return som3(u,a,c)+som3(u,c+1,b);
}:;

On pose :
u(n):=1/n
et
v(n):=1./n

Pour faire des calculs exacts, on tape :
evalf(som1(u,1,100000)) (Evaluation time: 22.6)
evalf(som2(u,1,100000)) (Evaluation time: 33.24)
evalf(som3(u,1,100000)) (Evaluation time: 29.92)
On obtient avec 24 digits :
0.1209014612986342794736320e2
Le résultat est bien sûr le même car les calculs sont faits de façon exacte et seule la réponse est donnée de façon approchée. som1 est plus rapide car on ajoute au début des fractions qui ont un petit dénominateur, som2 est plus lente car on ajoute au toujours des fractions qui ont un grand dénominateur et som3 est intermédiaire mais plutot plus lente car on fait appel à som3(u,c+1,b) où on ajoute des fractions qui ont un grand dénominateur à som3(u,a,c) qui elle aussi comporte des termes ayant un grand dénominateur.

Pour faire des calculs approchés, on tape :
som1(v,1,100000)
On obtient avec 24 digits (Evaluation time: 7.14) :
0.1209014612986342794736311e2
som2(v,1,100000)
On obtient avec 24 digits (Evaluation time: 7.16) :
0.1209014612986342794736294e2
som3(v,1,100000)
On obtient avec 24 digits (Evaluation time: 30.74) :
0.1209014612986342794736320e2
La procédure récursive est nettement plus longue à exécuter mais par contre elle donne un meilleur résultat.