principio di induzione

[danielem]

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} $

[Obidream]

Idee tue?

[gugo82]

Per idee generali su PIM puoi leggere qui.

[danielem]

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”…

[danielem]

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.

• 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.
  
  
• 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.

[danielem]

grazie gugo82, sei stato chiarissimo.