Metodo induttivo

Dimostrazione per induzione

Dimostrazione per P(m) è vero ∀m ∈ ℕ

Caso base: P(0) è vero.

Passo induttivo: P(m) ⇒ P(m+1) ∀m ∈ ℕ.

Esempio 1

Dimostriamo che:

1/2¹ + 2/2² + 3/2³ + ... + m/2ⁿ = (2^m+1 - m - 2) / 2ⁿ

Caso base: Se m = 0, S(m) = 0.

Passo induttivo: Sia m ≥ 0 e supponiamo che:

Abbiamo: S(m+1) = S(m) + (m+1)/2^m+1 = (2^m+1 - m - 2) / 2^m + (m+1)/2^m+1 = (2((2^m+1 - m - 2) / 2^m) + (m+1)/2^m+1) = (2((m+1-1) + (m+1)-2) / 2^m+1)

P(m+1) vale per qualsiasi numero n+1.

Induzione forte

Se:

1. P(0) è VERO

e anche

1. P(0) ∧ P(1) ∧ ... ∧ P(m) ⇒ P(m+1) ∀m ≥ 0

allora P(m) è VERA ∀m ∈ ℕ.

Dimostrazione per P(n) è vero ∀n ∈ ℕ

Caso base: P(0) è vero.

Passo induttivo: P(m) => P(m+1) ∀m ∈ ℕ.

Esempio 2

Dimostriamo che:

1/2¹ + 2/2² + 3/2³ + ... + m/2^m = (2^m+1 - m - 2)/2^m

Caso base: Se m = 0, S(m) = 0.

Passo induttivo: Sia m ≥ 0 e supponiamo che:

Abbiamo: S(m+1) = S(m) + (m + 1)/2^m+1 = (2^m+1 - m - 2)/2^m + (m + 1)/2^m+1 = (2(2^m+1 - m - 2)/2^m) = (2^(m+1)+1 - (m + 1) - 2)/2^m+1

P(m+1) vale per qualsiasi numero m+1.

Induzione in forma forte

Se:

1. P(0) è VERO

P(0) ∧ P(1) ∧ ... ∧ P(m) => P(m+1) ∀m ≥ 0

allora P(m) è VERA ∀m ∈ ℕ.

Calcolo del punteggio

Valore 4·4=16

Valore 5·3=15

Totale: 28 punti 16+4+3+2+1+1+1+1

Fra tutte le mosse possibili massimizzo il punteggio

Totale: 28 punti 16+4+4+2+1+1+1+1

Osservo che: qualsiasi sequenza mi darà lo stesso punteggio.

Dimostrazione per m ≥ 1

Qualsiasi sequenza di masse a partire da un mucchietto di m sassolini ha valore complessivo:

m·(m-1)₂

Dimostrazione per induzione

Caso base: Se m = 1 ogni sequenza di mosse vale ∅, perché di mosse non ne faccio, inoltre:

⁰⁄₂ = 0

2. Passo induttivo: sia m ≥ 1 e supponiamo che l’affermazione valga ∀ K ≤ m. Vogliamo far vedere che vale anche per ^m+1

Dato un mucchietto di m+1 sassi e l’altro con ^m+1-K sassi. Sia K ≤ m e ^m+1-K ≤ m

La prima mossa fatta vale K (^m+1-K) Inoltre, per ipotesi induttiva, il mucchietto di K sassi frutterà complessivamente (alla fine delle mosse) ^{K (K-1)}⁄₂ e il mucchietto di ^m+1-K sassi frutterà, in tutto ^{(m+1-K) (m+1-K-1)}⁄₂

Nel complesso, i punti fatti sono: ^{2K (m+1-K) + K (K-1) + (m+1-K) (m-K)}⁄₂ =