Somme notevoli

17/11/2020

Somme "notevoli"

Sono delle sommatorie che ricorrono molto spesso, al calcolo combinatorio:

1 + 2 + 3 + 4 + ... + m

1 + 4 + 9 + 16 + ... + m²

1 + 2 + 4 + 8 + 16 + ... + 2^m

si posso risolvere con delle funzioni, tramite formule chiuse:

Somma dei numeri naturali

_k=0∑^m k = _k=1∑^m k = S

GAUSS (matematico tedesco) doveva calcolare la somma di tutti i numeri da 1 a 100 1 + 2 + 3 + ... + 100, ricavò una formula generale

Approcio "geniale"

1 2 3 ... 99 100

100 99 98 ... 2 1

____________________

101 101 101 ... 101 101

2S = 100 . 101 ➔ S = 100 . 1012

= 10.100 = 50502

Generalizzo

1 2 ... m-1 m

m m-1 ... 2 1

____________________

m+1 m+1 ... m+1 m+1

17/11/2020

SOMME "NOTEVOLI"

Sono delle sommatorie che ricorrono molto spesso, al calcolo combinatorio:

• 1 + 2 + 3 + 4 + ... + m
• 1 + 4 + 9 + 16 + ... + m²
• 1 + 2 + 4 + 8 + 16 + ... + 2^m

si possono risolvere con delle funzioni, tramite formule chiuse:

SOMMA DEI NUMERI NATURALI

^m∑_k=0 K = ^m∑_k=1 K = S

GAUSS (matematico tedesco) doveva calcolare la somma di tutti i numeri da 1 a 1001 + 2 + 3 + ... + 100, ricavò una formula generale

Approccio "generale"

Generalizzo

2 ∑_κ=1^m κ = m (m+1)

∑_κ=1^m κ = m (m+1)/2

Approccio geometrico

AREA ROSSA + AREA VERDE AREA RETTANGOLO

2 A_rossa = A_tot

2S = m (m+1) ⇒ s = (m + 1) m / 2

Approccio analitico

La somma ha m termini ciascuno ≤ m ⇒ S ≤ m² I termini ≥ m/2 valgono ≥ m/2 ciascuno

⇒ S ≥ m/2 × m/2 = m²/4

m²/4 ≤ S ≤ m²

Ipotizziamo S = am² + bm + c vogliamo determinare a, b, c

a: 0² + b⋅0 + c = ∅ => c = ∅

a: 1² + b⋅1 = 1 => a + b = 1

a: 2² + b⋅2 = 3 => 4a + 2b = 3

{a + b = 14a + 2b = 3}

a = 1 - b4(1 - b) + 2b = 34 - 4b + 2b = 32b = 1 b = 1/2

b = 1/2

a = 1 - 1/2 = 1/2

c = ∅

¹/₂ m² + ¹/₂ m = ^{m(m + 1)}/₂

Si può dimostrare per induzione

Somma di quadrati

Σ_{k = 0}^m k²

Approccio geometrico

h = m + 1

b = ^{(m + 1)}⁄₂

A_TOT = b · h = ^{m (m + 1)2}⁄₂

A_TOT = A_G + A_B → A_G = A_TOT - A_B

In riga i, quanti quadratini bianchi ci sono?

∑ⁱ_k=1 k = ^{i (i + 1)}⁄₂ = ⁱ²⁄₂ + ⁱ⁄₂

Quanti quadratini bianchi in tutto?

A_B = ∑^m_i=1 (ⁱ²⁄₂ + ⁱ⁄₂) = ¹⁄₂ ∑^m_i=1 i² + ¹⁄₂ ∑^m_i=1 i

A_B = ¹⁄₂ A_n + ^{m (m + 1)}⁄₄

A_G = m ^{(m + 1)}⁄₂ - ¹⁄₂ A_G - m ^{(m + 1)}⁄₄

³⁄₂ A_G = m ^{(m + 1)}⁄₂ (m + 1 - ¹⁄₂)

A_G = m (m + 1) (^{2m + 2 - 1}⁄₂)

A_G = ^{m (m + 1) (2m + 1)}⁄₆

Se m = 0   A_G = 0

  m = 1   A_G = ^{1 · 2 · 3}⁄₆ = 1

  m = 2   A_G = ^{2 · 3 · 5}⁄₆ = 5

m = 3

A6 = ^{3 . 4 . 7}/₆ = 14

∑_{k = 1}^m k² = ^{m (m + 1) (2m + 1)}/₆

Approccio "analitico"

S = 1² + 2² + 3² + ... ≤ m² ≤ m²

(^m/₂)² + (^m/₂ + 1)² + ... + m² ≥ (^m/₂)²

ⁿ/₂ (^m/₂)² ≤ S ≤ m³

^m²/₈ ≤ S ≤ m³

S(m) = am³ + bm² + cm + d trovare a, b, c, d

S(0) = 0 ➔ d = 0

S(1) = 1 ➔ a + b + c = 1

S(2) = 5 ➔ 8a + 4b + 2c = 5

S(3) = 14 ➔ 27a + 9b + 3c = 14

{ a + b + c = 1 R₁ 8a + 4b + 2c = 5 R₂ 27a + 9b + 3c = 14 R₃}

R₁ + R₂ 9a + 5b + 3c = 6 R₄

R₃ - R₄ 18a + 4b = 8

R₂ - 2R₁ 6a + 2b = 3

{ 18a+4b = 8

6a+2b = 3

{ 9/2 a + b = 2 → b = 2 - 9/2 a

6a + 2b = 3

6a+2(2-9/2 a) = 3

6a+4-9a = 3

3a = 1 a = 1/3

{ a = 1/3

b = 2 - 9/6 = 1/2

c = 1-a-b → 1-1/3-1/2 = 6-2-3/6 = 1/6

a = 1/3 = 2/6 b = 1/2 = 3/6 c = 1/6

am³ + bm² + cm =

= 2/6 m³ + 3/6 m² + 1/6 m = 2m³+3m²+1m/6 =

= m (2m² + 3m + 1) /6 = m (m+1) (2m+1)/6

Somma potenze consecutive

Sia a > 1 ∈ R vogliamo calcolare

∑^m_k=0 a^k chiamiamola

S(m)

S(m+1) = a⁰ + a¹ + … + a^m + a^m+1

= S(m) + a^m+1