Dimostrazione per induzione

[*guitar_joker1]

Nel dimostrare per induzione questo esercizio:

Dimostrare che n<2^n per tutti gli n apparteneti ai numeri naturali.

Qual'è l'ipotesi induttiva che va utilizzata? grazie

[_luca.barletta]

come ipotesi induttiva userei proprio P(m): m<2^m

[amel3]

[size=75]Intanto si tratta di scegliere la convenzione che l'insieme dei numeri naturali $NN$ comprenda o meno lo 0... Io di solito non lo includo.[/size]

Il principio di induzione è il seguente:

Principio di induzione

Sia $P(n)$ una proposizione significativa per $n in NN$. Se:
1) $P(1)$ è vera.
2) $P(n)=>P(n+1)$.
Allora $P(n)$ è vera per ogni $n in NN$

In questo caso $P(n)={n<2^n}$, $forall n in NN$.

Soluzione:

1) $P(1)$ è vera: infatti $1<2^1=2$.

2) Supponiamo che sia vera $P(n)$ per un fissato $n in NN$.
Allora dobbiamo mostrare che sia vera $P(n+1)$.
Per ipotesi (ipotesi induttiva): $2^n>n$.
Ora usiamo l'ipotesi induttiva: $2^(n+1)=2^n*2>$(ip. indutt.)$2n>n+1$.
Da ciò si ottiene quanto si voleva.

Consiglio: prova a fare qualche altro esercizio e ti verrà tutto meccanicamente.

P.S.: Oggi (e non solo oggi) sono un po' groggy, per cui se c'è qualcosa di sbagliato correggete pure...

[*guitar_joker1]

grazie avete risolto il mio dubbio!!