SOLUZIONI DEGLI ESERCIZI SUL PRINCIPIO DI INDUZIONE

Esercizio 1

(a) ∑_{k=0}^{n} 2^{k} = 2^{n+1} − 1 P_{1} é vera, infatti per n = 1, 2^{0} + 2^{1} = 3 = 2^{1+1} − 1. Supponiamo vera P_{n} e dimostriamo P_{n+1}:

(2^{0} + 2^{1} + ...2^{n}) + 2^{n+1} = (2^{n+1} − 1) + 2^{n+1} = 2 · 2^{n+1} − 1 = 2^{n+2} − 1.

Abbiamo ottenuto P_{n+1}.

(b) ∑_{k=1}^{n} k = \frac{n(n+1)}{2} Verifichiamo P_{1} : 1 = \frac{1(1+1)}{2}. Supponiamo vera P_{n} e dimostriamo P_{n+1}:

1 + 2 + 3 + .... + n + (n + 1) = \frac{n(n + 1)}{2} + (n + 1) = \frac{(n + 1)(n + 2)}{2}.

Abbiamo ottenuto P_{n+1}.

(c) se a ≥ −1, (1 + a)^{n} ≥ 1 + na

Verifichiamo P_{1} : 1 + a = 1 + a. Supponiamo vera P_{n} e dimostriamo P_{n+1}:

(1+a)^{n+1} = (1+a)^{n}(1+a) ≥ (1+na)(1+a) = 1+a+na+na^{2} = 1+a(n+1)+na^{2} ≥ 1+a(n+1).

L’ ultima disuguaglianza deriva dal fatto che na^{2} ≥ 0. Abbiamo ottenuto P_{n+1}.

(d)n! ≥ 2^{n−1}

Verifichiamo P_{1} : 1 ≥ 1. Supponiamo vera P_{n} e dimostriamo P_{n+1}:

(n + 1)! = n!(n + 1) ≥ 2^{n−1}(n + 1) ≥ 2 · 2^{n−1} = 2^{n}.

Abbiamo ottenuto P_{n+1}.

(e) se a ≠ 1, ∑_{k=0}^{n} a^{k} = \frac{1−a^{n+1}}{1−a}

Verifichiamo P_{1} : ∑_{k=0}^{1} a^{k} = a^{0} + a^{1} = 1 + a. Supponiamo vera P_{n} e dimostriamo P_{n+1}:

∑_{k=0}^{n+1} = a^{0} + a^{1} + .... + a^{n} + a^{n+1} = \frac{1 − a^{n+1}}{1 − a} + a^{n+1} = \frac{1 − a^{n+2}}{1 − a} .

Abbiamo ottenuto P_{n+1}.

Esercizio 2 Riscriviamo la disuguaglianza come x^{\frac{1}{n}} ≤ 1 + \frac{x−1}{n}, ovvero x ≤ (1 + \frac{x−1}{n})^{n} . Grazie alla disuguaglianza di Bernoulli si ha:

(1 + \frac{x − 1}{n})^{n} ≥ 1 + n\frac{x − 1}{n} = x.

Esercizio 3 Ovviamente un numero pari si scrive come multiplo intero di 2, quindi la nostra tesi é dimostrare che n + n^{2} = 2k, k ∈ IN . Verifichiamo P_{1} : 1 + 1 = 2 é un numero pari. Suppongo vera P_{n}, cioé che n + n^{2} sia pari e dimostro P_{n+1}.

(n + 1) + (n + 1)^{2} = n + 1 + n^{2} + 2n + 1 = (n + n^{2}) + 2n + 2

poiché per ipotesi n + n^{2} é pari, il numero (n + n^{2}) + 2n + 2 é anch’ esso pari, e la tesi é dimostrata.

Esercizio 4 Usiamo l’induzione su n ≥ 1. Per n = 1 si ha x^{2} + x + 1 > 0 ∀x ∈ IR perché il discriminanate dell’equazione di secondo grado é negativo, quindi non ci sono intersezioni con l’asse reale. Supponiamo l’asserto vero per n e proviamolo per n + 1. Scriviamo la tesi, ovvero

x^{2n+2} + x^{2n+1} + (x^{2n}....... + x^{2} + x + 1) ≥ 0 ∀x ∈ IR, n ∈ IN .

(attenzione: ad ogni passo si aggiungono 2 termini alla sommatoria!!). La parte tra parentesi tonde é non negativa per ipotesi induttiva, quindi proviamo a studiare il segno di quello che rimane, ovvero x^{2n+2}+x^{2n+1} = x^{2n}(x^{2}+x). Poiché x^{2n} ≥ 0, ci riduciamo ulteriormente a studiare (x^{2} + x) = x(x + 1). Con pochi conti si vede che (x^{2} + x) ≥ 0∀x ∈ (−∞, −1) ∪ (0, +∞). Quindi avremmo risolto il problema ovunque tranne che nell’intervallo [−1, 0]. Facilmente si verifica (a mano!) che per x = −1, 0 l’asserto é vero. Per x ∈ (−1, 0) riprendiamo la disuguaglianza iniziale:

x^{2n+2} + x^{2n+1} + (x^{2n}....... + x^{2} + x + 1) = x^{2}(x^{2n}....... + x + 1) + x + 1

si ha: x^{2} ≥ 0, la somma (x^{2n}....... + x + 1) ≥ 0 per ipotesi induttiva, x + 1 ≥ 0 perché siamo nell’intervallo (−1, 0).

Esercizio 5 Per induzione su n. Per n = 1 S_{2^{1}} = 1 + \frac{1}{2} > \frac{1}{2}. Ora supponiamo vera la tesi per n, proviamola per n + 1.

S_{2^{n+1}} = S_{2^{n}} + \frac{1}{2^{n} + 1} + \frac{1}{2^{n} + 2} + ⋯ + \frac{1}{2^{n+1} − 1} + \frac{1}{2^{n+1}} .

E’ importante riuscire a capire quanti termini ci sono tra S_{2^{n+1}} e S_{2^{n}}. La differenza é composta esattamente da 2^{n} termini. Li possiamo stimare nel seguente modo (usiamo ora l’ipotesi induttiva):

S_{2^{n+1}} ≥ \frac{n}{2} + \frac{1}{2^{n} + 1} + \frac{1}{2^{n} + 2} + ⋯ + \frac{1}{2^{n+1} − 1} + \frac{1}{2^{n+1}} ≥

≥ \frac{n}{2} + 2^{n} (\frac{1}{2^{n+1}} ) = \frac{n}{2} + \frac{1}{2} = \frac{n + 1}{2}.