Successioni e induzione
Salve a tutti, vi espongo i miei dubbi relativi alle successioni definite ricorsivamente, presentando per aiutarmi nella esposizione di tali lacune, un'esercizio.
La domanda principale che vi pongo è come ricavare la forma non ricorsiva, ovvero la funzione $ f $:$ N -> R $, dalla forma ricorsiva; ad esempio, considerando la seguente definizione ricorsiva...
$AA n >= 0 $
$ { ( x_0 = 1 ),( x_(n+1) = 2 x_n ):} $
... posso scrivere i primi termini:
$x_0 = 1$
$x_1 = 2x_0 = 2$,
$x_2 = 2x_1 = 2*2 = 2^2$,
$x_3 = 2_x2 = 2*2*2 = 2^3$
da cui intuisco ( e sottolineo intuisco) che la mia $ f $:$ N -> R $ è della forma $ x_n = 2^n $.
Questa funzione però l'ho verificata solo per i primi 3 termini, e dunque non so se è sempre vera!
Stabilisco dunque la proposizione $ p(n) := $" $x_n = 2$ " $ AA n>=0 $ e per induzione dimostro che $ p(n) $ è vera; infatti:
$i) $ $p(0) := $"$x_0 = 2^0 = 1 $" vera
$ii) $ $p(n) => p(n+1)$ vera; basta considerare $x_(n+1) = 2x_n = 2*2^n = 2^(n+1)$
Dunque, riproponendo la mia domanda, per verificare che $ x_n = 2^n $ (ovvero la mia $ f $:$ N -> R $) è sufficiente aver dimostrato ciò?
Esposto il mio principale problema, vi propongo un'esercizio, in particolare l'esercizio che mi ha fatto sorgere queste tipo di domande, seguito da alcuni miei tentativi di risolverlo:
"Siano date n rette di un piano in posizione generica, $n >= 2 $ (2 rette qualsiasi si intersecano ma 3 qualsiasi non hanno un punto in comune). Sia $ p(n) $ il numero di parti in cui viene suddiviso il piano. Dimostrare che:
$i)$ $p(n+1) = p(n)+(n+1) $
$ii)$ $p(n) = (n^2+n+2) / 2$ "
Il blocco iniziale è che non capisco quali siano i miei "dati", ovvero cosa posso utilizzare come ipotesi; ho provato dunque a calcolarmi, a livello intuitivo ( disegnando le varie rette e contando le suddivisioni) i primi 5 termini:
$p(0) = 1$ , $p(1) = 2 $ , $p(2) = 4$ , $p(3) = 7$ , $p(4) = 11$
Da ciò non sono riuscito a concludere granchè... e dato che io devo dimostrare sia $i) $ che $ii)$ , ho provato a ragionare in tanti modi senza utilizzare nessuna delle due come ipotesi; infatti la $ii)$ l'ho verificata solo per i primi 5 termini, e per verificarla $AA n>=2 $ dovrei utilizzare la $i)$ che appunto non riesco a dimostrare (se non tramite la $ii$!!).
Infatti un'ulteriore osservazione che ho fatto è la seguente:
Considero $p(n+1) = p(n)+(n+1)$;
Sostituendoci $p(n)$ trovo:
$(n^2+n+2)/2+(n+1) =$
$(n^2+n+2+n2+2)/2 =$
//raccogliendo i giusti termini://
$((n^2+2n+1)+(n+1)+2)/2 =$
$((n+1)^2+(n+1)+2)/2$ che è proprio $p(n+1)$ ottenuta cambiando l'argomento a $p(n)$
In conclusione non sono riuscito a dimostrare niente; qualcuno sa aiutarmi?
PS:Mi scuso in anticipo per eventuali errori di terminologia.
PSPS:Grazie in anticipo e dio benedica voi e questo forum!
PSPSPS:Mi scuso inoltre per aver utilizzato fino ad ora il forum solo per esporre dubbi, ma tra la mie scarse conoscenze e la vostra efficenza e velocità nel rispondere ai post altrui, per me è arduo ad oggi poter aiutare altri in questo campo
La domanda principale che vi pongo è come ricavare la forma non ricorsiva, ovvero la funzione $ f $:$ N -> R $, dalla forma ricorsiva; ad esempio, considerando la seguente definizione ricorsiva...
$AA n >= 0 $
$ { ( x_0 = 1 ),( x_(n+1) = 2 x_n ):} $
... posso scrivere i primi termini:
$x_0 = 1$
$x_1 = 2x_0 = 2$,
$x_2 = 2x_1 = 2*2 = 2^2$,
$x_3 = 2_x2 = 2*2*2 = 2^3$
da cui intuisco ( e sottolineo intuisco) che la mia $ f $:$ N -> R $ è della forma $ x_n = 2^n $.
Questa funzione però l'ho verificata solo per i primi 3 termini, e dunque non so se è sempre vera!
Stabilisco dunque la proposizione $ p(n) := $" $x_n = 2$ " $ AA n>=0 $ e per induzione dimostro che $ p(n) $ è vera; infatti:
$i) $ $p(0) := $"$x_0 = 2^0 = 1 $" vera
$ii) $ $p(n) => p(n+1)$ vera; basta considerare $x_(n+1) = 2x_n = 2*2^n = 2^(n+1)$
Dunque, riproponendo la mia domanda, per verificare che $ x_n = 2^n $ (ovvero la mia $ f $:$ N -> R $) è sufficiente aver dimostrato ciò?
Esposto il mio principale problema, vi propongo un'esercizio, in particolare l'esercizio che mi ha fatto sorgere queste tipo di domande, seguito da alcuni miei tentativi di risolverlo:
"Siano date n rette di un piano in posizione generica, $n >= 2 $ (2 rette qualsiasi si intersecano ma 3 qualsiasi non hanno un punto in comune). Sia $ p(n) $ il numero di parti in cui viene suddiviso il piano. Dimostrare che:
$i)$ $p(n+1) = p(n)+(n+1) $
$ii)$ $p(n) = (n^2+n+2) / 2$ "
Il blocco iniziale è che non capisco quali siano i miei "dati", ovvero cosa posso utilizzare come ipotesi; ho provato dunque a calcolarmi, a livello intuitivo ( disegnando le varie rette e contando le suddivisioni) i primi 5 termini:
$p(0) = 1$ , $p(1) = 2 $ , $p(2) = 4$ , $p(3) = 7$ , $p(4) = 11$
Da ciò non sono riuscito a concludere granchè... e dato che io devo dimostrare sia $i) $ che $ii)$ , ho provato a ragionare in tanti modi senza utilizzare nessuna delle due come ipotesi; infatti la $ii)$ l'ho verificata solo per i primi 5 termini, e per verificarla $AA n>=2 $ dovrei utilizzare la $i)$ che appunto non riesco a dimostrare (se non tramite la $ii$!!).
Infatti un'ulteriore osservazione che ho fatto è la seguente:
Considero $p(n+1) = p(n)+(n+1)$;
Sostituendoci $p(n)$ trovo:
$(n^2+n+2)/2+(n+1) =$
$(n^2+n+2+n2+2)/2 =$
//raccogliendo i giusti termini://
$((n^2+2n+1)+(n+1)+2)/2 =$
$((n+1)^2+(n+1)+2)/2$ che è proprio $p(n+1)$ ottenuta cambiando l'argomento a $p(n)$
In conclusione non sono riuscito a dimostrare niente; qualcuno sa aiutarmi?
PS:Mi scuso in anticipo per eventuali errori di terminologia.
PSPS:Grazie in anticipo e dio benedica voi e questo forum!
PSPSPS:Mi scuso inoltre per aver utilizzato fino ad ora il forum solo per esporre dubbi, ma tra la mie scarse conoscenze e la vostra efficenza e velocità nel rispondere ai post altrui, per me è arduo ad oggi poter aiutare altri in questo campo
Risposte
Per dimostrare la ii) ragionamento induttio va benissimo, manca solo un'ipotesi inziale, cioè che ad esempio $p(2)=4$, ed è verificate perchè due rette che si incrociano dividono il piano in 4 parti.
Dimostrare la i), mi sembra tutt'altro che banale. Innanzitutto si nota subito che le rette non devono essere a due a due parallele e le intersezioni devono essere a due a due disgiunte, altrimenti è facile trovare dei controesempi per cui la i) fallisce.
Intuitiamente non è difficile vedere perchè òla i) è vera, però non saprei darti una dimostrazione rigorosa.
Dimostrare la i), mi sembra tutt'altro che banale. Innanzitutto si nota subito che le rette non devono essere a due a due parallele e le intersezioni devono essere a due a due disgiunte, altrimenti è facile trovare dei controesempi per cui la i) fallisce.
Intuitiamente non è difficile vedere perchè òla i) è vera, però non saprei darti una dimostrazione rigorosa.
"GabMat":
La domanda principale che vi pongo è come ricavare la forma non ricorsiva, ovvero la funzione $ f $:$ N -> R $, dalla forma ricorsiva; ad esempio, considerando la seguente definizione ricorsiva...
$ AA n >= 0 $
$ { ( x_0 = 1 ),( x_(n+1) = 2 x_n ):} $
... posso scrivere i primi termini:
$ x_0 = 1 $
$ x_1 = 2x_0 = 2 $,
$ x_2 = 2x_1 = 2*2 = 2^2 $,
$ x_3 = 2_x2 = 2*2*2 = 2^3 $
da cui intuisco ( e sottolineo intuisco) che la mia $ f $:$ N -> R $ è della forma $ x_n = 2^n $.
Questa funzione però l'ho verificata solo per i primi 3 termini, e dunque non so se è sempre vera!
Stabilisco dunque la proposizione $ p(n) := $" $ x_n = 2 $ " $ AA n>=0 $ e per induzione dimostro che $ p(n) $ è vera; infatti:
$ i) $ $ p(0) := $"$ x_0 = 2^0 = 1 $" vera
$ ii) $ $ p(n) => p(n+1) $ vera; basta considerare $ x_(n+1) = 2x_n = 2*2^n = 2^(n+1) $
Dunque, riproponendo la mia domanda, per verificare che $ x_n = 2^n $ (ovvero la mia $ f $:$ N -> R $) è sufficiente aver dimostrato ciò?
Beh, sì.
Infatti, prova a guardare cosa hai dimostrato.
Innanzitutto, hai fatto vedere che il problema:
\[
\tag{R}
\begin{cases}
x_{n+1} = 2\ x_n\\
x_0=1
\end{cases}
\]
ha qualche soluzione, perché ne hai esibita una esplicitamente (cioé la successione di termine generale \(2^n\)); quindi l'insieme delle successioni che risolvono (R) non è vuoto.
A ben vedere, quindi, risultato di unicità è tutto ciò che ti manca per poter affermare che quella di termine generale \(2^n\) è l'unica soluzione di (R).
Per mostrare l'unicità, basta far vedere che una qualsiasi successione \((x_n)\) che soddisfa (R) coincide necessariamente con \(2^n\), i.e. che \(x_n=2^n\) per ogni \(n\in \mathbb{N}\); questa ultima proprietà puoi esprimerla insiemisticamente mediante l'uguaglianza:
\[
C:=\big\{ n\in \mathbb{N}:\ x_n=2^n\big\} = \mathbb{N}\; ,
\]
la quale ti dice che l'insieme \(C\) degli indici sui quali le due successioni \((x_n)\) ed \((2^n)\) coincidono è uguale a tutto \(\mathbb{N}\).
Per stabilire l'uguaglianza \(C=\mathbb{N}\) puoi, anzi devi, usare l'induzione: infatti, per la stessa definizione di \(\mathbb{N}\), ti basta mostrare che 1 \(0\in C\) e che 2 \(n\in C\Rightarrow n+1 \in C\) per avere \(C=\mathbb{N}\).
Ora, la 1 equivale alla i \(x_0=2^0\), mentre la 2 equivale a ii \(x_n=2^n\Rightarrow x_{n+1}=2^{n+1}\); quindi ti basta mostrare i e ii per avere \(x_n=2^n\) per ogni \(n\in \mathbb{N}\).
La verifica di i è immediata, perché \(x_0=1=2^0\) essendo \((x_n)\) una soluzione di (R); mentre, supponendo vera l'uguaglianza \(x_n=2^n\), dalla equazione ricorsiva si trae \(x_{n+1}=2 x_n=2\ 2^n=2^{n+1}\), e ciò prova che vale la ii. Per il principio d'induzione hai \(C=\mathbb{N}\) e dunque \(x_n=2^n\)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo