22. ESERCIZI SVOLTI SUL PRINCIPIO DI INDUZIONE MATEMATICA
|
Principio di induzione matematica:
SE una proprietà P(x), il cui insieme ambiente sia N:
ALLORA quella proprietà vale per ogni numero naturale.
|
|
Per dimostrare, applicando tale Principio, che una data proprietà P(x) vale per ogni x appartenente ad N, si procede nel modo seguente:
a) si verifica che la proprietà P(x) vale con x=0;
b) si suppone, come ipotesi di lavoro, che la proprietà valga con x=k, e si dimostra che, sotto questa ipotesi, la proprietà deve necessariamente valere anche con x=k+1.
a) e b) garantiscono, per il Principio di induzione matematica, che la proprietà P(x) vale su tutto N.
Un’ovvia variante consiste nel “partire da 1” anziché da zero.
|
Esercizio 1)
Dimostriamo che
applicando il “principio di Induzione Matematica”
(precisamente, la sua variante in N*, ossia la variante che parte da 1 anziché da 0)
a)
L’uguaglianza da dimostrare è verificata con x=1? Vediamo.
Con x=1, l’uguaglianza da dimostrare diventa
che è vera!
b)
Supponiamo che l’uguaglianza da dimostrare sia vera con x=k:
supponiamo cioè che si abbia
Ci chiediamo: essa sarà ancora vera anche per x=k+1? Andiamo a vedere.
Partiamo dal primo membro dell’uguaglianza da dimostrare, ponendo x=k+1,
e utilizziamo l’ “ipotesi induttiva” .
Avremo:
Pertanto: l’uguaglianza da dimostrare è vera con k=1,
e, qualora sia vera con x=k, continua certamente a valere anche per x=k+1:
perciò, è vera per x=2, x=3, x=4, x=5, x=6, x=7, … insomma: è vera per ogni numero naturale (non nullo).
Esercizio 2)
Dimostriamo che
tramite il “principio di Induzione Matematica” .
Anche in questo caso, evidentemente, partiremo da 1 anziché da 0.
a)
L’uguaglianza da dimostrare è verificata con x=1?
Con x=1, essa diventa
che è vera!
b)
Supponiamo che l’uguaglianza da dimostrare sia vera con x=k:
supponiamo cioè che si abbia
Ci chiediamo: essa sarà ancora vera anche per x=k+1?
Il P.I.M. ci consente a questo punto di affermare che l’uguaglianza proposta è effettivamente vera per ogni numero naturale non nullo.
Esercizio 3)
Applicando il “principio di Induzione Matematica” , dimostriamo che:
NOTA:
Ricordiamo che
l’ “insieme delle parti” di un dato insieme A, è quell’insieme i cui elementi
sono i sottoinsiemi di A; ad esempio, se
,
è
a)
La proprietà da dimostrare è vera per n=0?
Per n=0, l’insieme A è privo di elementi: .
L’insieme è dunque, in questo caso,
,
vale a dire l’insieme i cui elementi sono i sottoinsiemi dell’insieme vuoto.
Ma l’insieme vuoto ha uno e un solo sottoinsieme: se stesso.
Perciò (l’insieme, il cui unico elemento è l’insieme
vuoto).
A conteneva n=0 elementi; abbiamo visto che contiene 1 elemento.
Ma .
Perciò la proprietà da dimostrare è vera quando n=0.
b)
Supponiamo che la proprietà da dimostrare sia vera per un certo numero naturale k:
supponiamo cioè che, ogniqualvolta un insieme A
contiene k elementi, il suo insieme delle parti contenga
elementi (in altre parole: supponiamo che un
insieme di k elementi abbia
sottoinsiemi).
Questa è la nostra ipotesi induttiva:
“se un insieme A contiene k elementi, allora
possiede sottoinsiemi”.
Vogliamo ora far vedere che, sotto tale ipotesi, la proprietà deve continuare a valere anche per k+1, ossia: che
“un insieme contenente k+1 elementi deve avere
necessariamente sottoinsiemi.”
In effetti:
un insieme B che abbia k+1 elementi, può essere pensato come ottenibile a partire da un insieme A contenente k elementi, al quale venga aggiunto un nuovo elemento w.
Ora, per contare i
sottoinsiemi di ,
possiamo suddividerli in due categorie:
· quelli che non contengono w
· quelli che contengono w
Ma i sottoinsiemi
della prima categoria sono tutti e soli i sottoinsiemi di A! Quindi il loro
numero è, per l’ipotesi induttiva, .
Pensiamo ora ai sottoinsiemi della seconda categoria.
Osserviamo che se prendiamo uno di questi sottoinsiemi, e gli togliamo w, otterremo un sottoinsieme di A!
Quindi i sottoinsiemi
della seconda categoria sono tutti e soli quegli insiemi, ottenibili partendo
da uno dei sottoinsiemi di A, e aggiungendogli
l’elemento w.
Pertanto anche i
sottoinsiemi della seconda categoria sono (tanti quanti i sottoinsiemi di A).
E in totale, i
sottoinsiemi di B sono .
La dimostrazione è così completata.