Principio di induzione

danielem1
Mi sembrava un esercizio banale, a prima vista, però mi sta mettendo in seria difficoltà, l'esercizio è il seguente:

dimostrare con il principio di induzione che $ 2n<= 2^n $ , $ nin NN - {0} $

Risposte
Obidream
Idee tue?

gugo82
Per idee generali su PIM puoi leggere qui.

danielem1
Obidream, cosa intendi con idee tue? se l'esercizio è una mia idea o se ho qualche idea su come risolverlo? nel primo caso no, è un esercizio di testo, nel secondo caso, l'unica idea che mi è venuta è di applicare il principio per (n+1), ma non arrivo ad ottenere l'espressione che mi verifichi al disuguaglianza.

gugo82
Intende: tu cosa hai provato a fare?

La cosa mi sembra semplice, no?
Parti da $2^(n+1)$ e cerca di usare l’ipotesi induttiva per “scendere”…

danielem1
ho fatto così:
$ 2(n+1)<= 2^(n+1) $
$ 2(n+1)<= 2^n*2 $
$ (n+1)<= 2^n $
quindi:
$ (n+1)<= n+n=2n<= 2^n $
segue:
$ 2(n+1)<= 2^n*2=2^(n+1) $

è corretto il ragionamento?

gugo82
Nì…

Il problema è che se parti da $2(n+1) <= 2^(n+1)$ sembra tu stia assumendo già vera la tesi, e ciò è male.

Una linea di ragionamento corretta è la seguente.


    [*:1fihcck0] Innanzitutto, osserviamo che la disuguaglianza $2n <= 2^n$ è vera per $n=0$ ed $n=1$, poiché sostituendo si trova:
    \[
    \begin{split}
    n=0\quad \to \quad 2\cdot 0 = 0 &\leq 1 =2^0 \\
    n=1 \quad \to \quad 2\cdot 1 = 2 &\leq 2 =2^1\; .
    \end{split}
    \]
    Questa è una buona base per l’induzione.

    [/*:m:1fihcck0]
    [*:1fihcck0]Ci rimane da dimostrare il passo induttivo, cioè da provare che se la disuguaglianza $2n <= 2^n$ è vera per un certo $n>=1$ (questa è l’ipotesi induttiva) allora essa è vera pure per $n+1$, cioè risulta $2(n+1) <= 2^(n+1)$ (questa è la tesi induttiva).
    Partendo da $2^(n+1)$ e sfruttando le proprietà delle potenze e l’ipotesi induttiva troviamo:
    \begin{align*}
    2^{n+1} &= 2 \cdot \underbrace{2^n}_{\geq 2n} & & \text{(proprietà delle potenze)} \\
    &\geq 2\cdot 2n & & \text{(per ipotesi induttiva e proprietà di } \geq \text{)} \\
    &= 2n + \underbrace{2n}_{\geq 2} & & \text{(per definizione del “doppio”)} \\
    &\geq 2n + 2 & & \text{(perché } n \geq 1 \Rightarrow 2n \geq 2 \text{ e proprietà di } \geq \text{)} \\
    &= 2(n+1) & & \text{(per raccoglimento a fattore comune)}\; ,
    \end{align*}
    cosicché, tralasciando i passaggi intermedi e leggendo dal basso verso l’alto, abbiamo $2(n+1) <= 2^(n+1)$ che è la tesi. 8-)[/*:m:1fihcck0][/list:u:1fihcck0]

danielem1
grazie gugo82, sei stato chiarissimo.

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.