Esercizi sul principio di induzione - parte 3
Indice esercizi (corso Analisi Matematica 1)
Usando il principio di induzione dimostrare che
- $n!>2^{n}$ per ogni $n\in\mathbb{N}$ e $n\geqslant4$
- $\sum\limits_{k=1}^n k^2 > {n^3\over 3}$
- $(1+x)^{n}\geqslant 1+nx\quad\forall n\in\mathbb{N}$, $x\in\mathbb{R}$ e $x>-1$ (disuguaglianza di Bernoulli)
- ${n \choose k} \in\mathbb{N}$ (con sugg.)
- $\sum\limits_{k=0}^{n-1}k^p < \frac {n^{p+1}}{p+1} < \sum\limits_{k=0}^{n}k^p$ con $p\geqslant 1$ (con sugg.)
Gli esercizi 4 e 5 sono molto difficili
Esercizi
Esercizio 1
Usando il principio di induzione dimostrare che $${n!>2^{n}}$$ per ogni $n\in\mathbb{N}$ e $n\geqslant4$
Soluzione (passo base)
Per $n=4$ si ha $4! > 2^4$ è vera perché $24 > 16$
Soluzione (passo induttivo)
$$(n+1)! = (n+1)n! > (n+1)2^{n}$$
Ora, per $n\geqslant4$ si ha $n+1>2$ e quindi $$(n+1)! > (n+1)2^{n} > 2 \cdot 2^{n}= 2^{n+1}$$
Esercizio 2
Usando il principio di induzione dimostrare che $${\sum\limits_{k=1}^n k^2 > {n^3\over 3}}$$
Soluzione (passo base)
Per $n=1$ si ha $$\sum\limits_{k=1}^1 k^2 = 1 > {1^3\over 3} = {1\over 3}$$
Soluzione (passo induttivo)
$$\begin{aligned} \sum\limits_{k=1}^{n+1} k^2 &= \sum\limits_{k=1}^n k^2 + (n+1)^2 \;>\; {n^3\over 3} + (n+1)^2 \\ &= {1\over 3}\left(n^3 + 3n^2+6n+3\right)\\ & \color{white}{\text{(completo il cubo)}}\\ &= {1\over 3}\left((n+1)^3 -3n^2 -3n -1 + 3n^2+6n+3\right)\\ &= {1\over 3}\left((n+1)^3 + \underbrace{(3n+2)}_{>0}\right) \;>\; {(n+1)^3\over 3} \end{aligned}$$
Esercizio 3 (disuguaglianza di Bernoulli)
Sia $x\in\mathbb{R}$ e $x>-1$. Usando il principio di induzione dimostrare che $${(1+x)^{n}\geqslant 1+nx\quad\forall n\in\mathbb{N}}$$
Soluzione (passo base)
Per $n=0$, si ha $$ (1+x)^0 = 1 \geqslant 1+0\cdot x = 1 $$ che risulta vera per ogni $x>-1$
Soluzione (passo induttivo)
$$\begin{aligned} (1+x)^{n+1} &= (1+x)^n(1+x) \\ &\color{white}{\text{(usando l'ipotesi induttiva si ha)}}\\ &\geqslant (1+nx)(1+x) \\ &\geqslant 1+x + nx + nx^2 \\ &\color{white}{\text{($n$ è un naturale e $x^2$ un termine positivo per cui $nx^2\geqslant0$ quindi)}}\\ &\geqslant 1+x + nx\\ &\geqslant 1 + (n+1)x \end{aligned}$$
Esercizio 4
Usando il principio di induzione dimostrare che $${{n \choose k} \in\mathbb{N}}$$ (suggerimento: induzione su $s=n+k$)
Soluzione (passo base)
Da $s=n+k$ e $s=0$ si ha $n=k=0$ quindi
$$ {n \choose k} = {0 \choose 0} = 1 $$
Nota:
Useremo il principio di induzione nella seconda forma
Soluzione (passo induttivo)
Sia $k\leqslant n$. Dobbiamo dimostrare che ${n \choose k}\in\mathbb{N}$ con con $s+1 = n+k$ sapendo per ipotesi induttiva che ${n \choose k}\in\mathbb{N}$ con $s=n+k$
Dalla formula $$ {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k} $$ si ha
- $n+k = s+1$
- $n-1 + (k-1) = n+k-2 = s-1$
- $n-1 + k = n+k-1 = s$
Quindi, per l'ipotesi induttiva abbiamo che ${n-1 \choose k-1}\in\mathbb{N}$ e ${n-1 \choose k}\in\mathbb{N}$
Essendo ${n \choose k}$ la somma di due naturali è ancora un naturale.
Esercizio 5
Sia $p\geqslant 1$. Usando il principio di induzione dimostrare che $${\sum\limits_{k=0}^{n-1}k^p < \frac {n^{p+1}}{p+1} < \sum\limits_{k=0}^{n}k^p}$$
Nota: Questa diseguaglianza sarà chiara quando faremo gli integrali
Suggerimento:
Per la prima diseguaglianza usare lo sviluppo del binomio di Newton applicato a $(n+1)^{p+1}$ e arrestato ai primi due termini
Per la seconda diseguaglianza usare: $a^p-b^p=(a-b)\sum\limits_{k=0}^{p-1}a^kb^{p-k-1}$ e poi dividere per $(n+1)^{p-k}$
Soluzione (passo base)
Per $n=1$ le diseguaglianze diventano
$$ \sum\limits_{k=0}^{1-1}k^p < \frac{1^{p+1}}{p+1} < \sum\limits_{k=0}^{1}k^p \implies 0 < \frac{1}{p+1} < 1 $$
che è vera per $p\geqslant 1$
Soluzione (passo induttivo): prima diseguaglianza (premessa)
Osserviamo che
$$ (n+1)^{p+1} = n^{p+1} + (p+1)n^p + P_{p-1}(n) $$
dove $P_{p-1}(n)$ è un polinomio in $n$ di grado $p-1$ e sempre positivo, i.e.
$$ P_{p-1}(n) > 0 $$
Quindi si ha
$$ (n+1)^{p+1} > n^{p+1} + (p+1)n^p \iff {{n^{p+1}\over p+1} + n^p < {(n+1)^{p+1}\over p+1}} $$
Soluzione (passo induttivo): prima diseguaglianza
$$\begin{aligned} \sum\limits_{k=0}^{n}k^p &= \sum\limits_{k=0}^{n-1}k^p + n^p \\ &\color{white}{\text{(passo induttivo)}}\\ & < {n^{p+1}\over p+1} + n^p\\ &\color{white}{\text{(diseguaglianza precedente)}}\\ & < {(n+1)^{p+1}\over p+1} \end{aligned}$$
Soluzione (passo induttivo): seconda diseguaglianza
Dalla formula $a^p-b^p=(a-b)\sum\limits_{k=0}^{p-1}a^kb^{p-k-1}$ e ricordando che $0 < {n\over n+1}< 1$ si ha
$$\begin{aligned} (n+1)^{p+1}-n^{p+1} &= \sum\limits_{k=0}^{p}(n+1)^k n^{p-k} \\ &\color{white}{\text{divido e moltiplico per } (n+1)^{p-k}}\\ & = \sum\limits_{k=0}^{p} (n+1)^{p} \left({n\over n+1}\right)^{p-k} \;<\; \sum\limits_{k=0}^{p} (n+1)^{p} \;=\; (p+1) (n+1)^{p} \end{aligned}$$
da cui
$$ (n+1)^{p+1}-n^{p+1} < (p+1) (n+1)^{p} \iff {\frac{n^{p+1}}{p+1} + (n+1)^p > \frac{(n+1)^{p+1}}{p+1}} $$
Soluzione (passo induttivo): seconda diseguaglianza
:::{.old} $$ \frac {n^{p+1}}{p+1} < \sum\limits_{k=0}^{n}k^p \quad,\quad \frac{n^{p+1}}{p+1} + (n+1)^p > \frac{(n+1)^{p+1}}{p+1} $$ :::
$$\begin{aligned} \sum\limits_{k=0}^{n+1}k^p &= \sum\limits_{k=0}^{n}k^p + (n+1)^p \\ &\color{white}{\text{(passo induttivo)}}\\ & > \frac{n^{p+1}}{p+1} + (n+1)^p\\ &\color{white}{\text{(diseguaglianza precedente)}}\\ & > \frac{(n+1)^{p+1}}{p+1} \end{aligned}$$
Ricorda di sostenere questo progetto con una donazione (PayPal.Me/ManoloVenturin).