Analisi 1 Teoria "Principio di Induzione e Calcolo Combinatorio" [cap. II]

Capitolo 2

Principio di induzione e calcolo combinatorio

Il principio di induzione

• Serve a dimostrare che una certa formula è valida per un qualsiasi numero naturale "n".

Es:

Vogliamo provare che la somma dei primi N "n" :

S_n = 1 + 2 + 3 + ... + n vale n(n+1)/2

Perciò:

∀n ∈ ℕ P(n) è vero

P(u): S_n

Il principio di induzione afferma che se valgono le seguenti condizioni:

1. P(1) è vera
2. ∀n ∈ ℕ P(n) ⇒ P(n+1)

Allora:

∀n ∈ ℕ P(n) è vera

Nell'esempio dato:

I) P(i) è vero? n=1

S₁ = ¹⁄₂(1+1) = 1 Vero

II) P(n) → P(n+1)   ∀ n ∈ N

Supponendo   S_n = ⁿ⁽ⁿ⁺¹⁾⁄₂   devo provare che   S_n+1 = ^(n+1)(n+2)⁄₂

Infatti:

S_n+1 = ⁿ⁽ⁿ⁺¹⁾⁄₂ → S_n+1 = ⁿ⁽ⁿ⁺¹⁾⁄₂ + (n+1) = ¹⁄₂(n+1)(n+2)

Questa formula vale per ogni n ∈ N

Come derivare alla formula?

In modo diretto

S_n = 1 + 2 + 3 + 4 + ... + N =

= N + (N-1) + (N-2) + (N-3) + ... + 1 =

2S_n = (n+1) + (n+1) + (n+1) + (n+1) + ... + (n+1)

S_n = ⁿ⁽ⁿ⁺¹⁾⁄₂

Esercizio 2 Disuguaglianza di Bernoulli

Sia d ≥ 1, vogliamo provare:

(1+d)ⁿ ≥ 1+nd   P(n)

I) P(i) vero?

(1+d)¹ ≥ 1 + d   Vero

II) P(n) → P(n+1)   ∀ n ∈ N

(1+d)ⁿ ≥ 1 + nd → (1+d)ⁿ(1+d) ≥ (1+nd)(1+d)

Parliamo di:

Disposizioni Semplici di classe k, nel nostro esempio:

• n = 5 k=3
• D(5,3)=?

dato n ∈ ℕ osserviamo che:

- D(n,1)=n banalmente.

- D(n,k) = D(n-₁,k-₁).?

A ogni disposizione di k-₁ oggetti mi giunge per completameto -1 n-k+₁. Disposiz. di classe k devo scegliere tra gli n-(k-₁) = n-k+₁ oggetti rimasti.

pertanto:

• D(n,1)=n
• D(n,2)=n(n-1)
• D(n,k) = n(n-₁)(n-₂)... (n-k+₁)

nel nostro caso

• D(5,3) = 5*4*3=60

*DEFINIZIONE*

La disposizione semplice è un'applicazione iniettiva da un insieme di k elementi ad un insieme di n elementi.

Esempio 2

4 persone si devono disporre in una fila da 7 poltrone. In quanti modi possono farlo.

• D(7,4) = 7*6*5*4 = 840