Dimostrazione di una relazione di ricorrenza
Ciao a tutti! Ho difficoltà nel dimostrare la relazione di ricorrenza:
$G(n)=\{(1\text{ per } n=0),(2\text{ per } n=1),(G(n-1)+2G(n-2)\text{ per } n>1):}$
a. Trovare i valori di $G(n)$ per $n=2,3,4,5$
Trovati:
n=2 -> 2 + 2 =4
n=3 -> 4 + 4 =8
n=4 -> 8 + 8 =16
n=5 -> 16 + 16 = 32
Quindi si può concludere che $G(n) = 2^n$
b. Dal punto precedente intuire la relazione esatta e dimostrarla per induzione.
per induzione G(0) e G(1) verificano la relazione conclusa.
Assumendo $G(n)=2^n$ devo dimostrare che $G(n+1)=2^(n+1)$
Purtroppo mi blocco perché provando a svolgere: $G(n+1)= 2^(n+1) = 2G(n)$ Ma $G(n+1)=G(n)+2G(n-1)=2^n+2G(n-1)=2G(n)$ ma $G(n-1)$ non lo conosco.
----------------MODIFICA------------------------------------------------------
Però si nota dall'ultima espressione che vale $G(n)=2G(n-1)$
Quindi quindi $G(n-1)=\frac{G(n)}{2}=2^{n-1}$ (perché $G(n)$ ce l'ho)
Allora
$G(n+1)=G(n)+2G(n-1)=2^n+2*2^{n-1}=2^{n+1}$
Così può andare no? O era più semplice?
---------------FINE MODIFICA-------------------------------------------------
In ogni caso col metodo delle differenze finite:
$y^2-y-2=0 \implies y_1=-1, y_2=2$ Quindi una soluzione del tipo $y=A(-1)^n+B2^n$
Sostituendo le soluzioni particolari: $A+B=1$ e $-A+2B=2 -> A=0$ mentre $B = 1$, quindi $y=2^n$
Non ho mai fatto esercizi sull'induzione è giusto come l'ho risolto quello prima secondo voi? Mi è venuta l'idea la mattina dopo
$G(n)=\{(1\text{ per } n=0),(2\text{ per } n=1),(G(n-1)+2G(n-2)\text{ per } n>1):}$
a. Trovare i valori di $G(n)$ per $n=2,3,4,5$
Trovati:
n=2 -> 2 + 2 =4
n=3 -> 4 + 4 =8
n=4 -> 8 + 8 =16
n=5 -> 16 + 16 = 32
Quindi si può concludere che $G(n) = 2^n$
b. Dal punto precedente intuire la relazione esatta e dimostrarla per induzione.
per induzione G(0) e G(1) verificano la relazione conclusa.
Assumendo $G(n)=2^n$ devo dimostrare che $G(n+1)=2^(n+1)$
Purtroppo mi blocco perché provando a svolgere: $G(n+1)= 2^(n+1) = 2G(n)$ Ma $G(n+1)=G(n)+2G(n-1)=2^n+2G(n-1)=2G(n)$ ma $G(n-1)$ non lo conosco.
----------------MODIFICA------------------------------------------------------
Però si nota dall'ultima espressione che vale $G(n)=2G(n-1)$
Quindi quindi $G(n-1)=\frac{G(n)}{2}=2^{n-1}$ (perché $G(n)$ ce l'ho)
Allora
$G(n+1)=G(n)+2G(n-1)=2^n+2*2^{n-1}=2^{n+1}$
Così può andare no? O era più semplice?
---------------FINE MODIFICA-------------------------------------------------
In ogni caso col metodo delle differenze finite:
$y^2-y-2=0 \implies y_1=-1, y_2=2$ Quindi una soluzione del tipo $y=A(-1)^n+B2^n$
Sostituendo le soluzioni particolari: $A+B=1$ e $-A+2B=2 -> A=0$ mentre $B = 1$, quindi $y=2^n$
Non ho mai fatto esercizi sull'induzione è giusto come l'ho risolto quello prima secondo voi? Mi è venuta l'idea la mattina dopo
Risposte
Ti stai perdendo in un bicchiere d'acqua. Devi usare il principio di induzione forte.
Grazie per la risposta. Non l'ho mai visto e da quello che ho letto usando questo principio quando dico che $G(n)=2^n$ dico anche che $G(n-1)=2^{n-1}$ quindi per la verifica al caso $n+1$ basta che faccia $G(n+1)=2^n+2^n=2^{n+1}$ Fine..?
Beh, sostanzialmente si. Ma andrebbe esposto in maniera un po' più corretta formalmente.
Grazie, devo leggermi meglio questi argomenti
Quando fai uso dell'induzione supponi ad un certo punto che \( G(n) = 2^n \; \forall n \leq k. \) Dici insomma che la relazione vale fino ad un certo punto e provi che da questa ipotesi puoi stabilire che la relazione vale anche per \(n = k+1\) da cui puoi quindi concludere che la relazione vale per ogni \(n\).
Grazie sei stato molto chiaro 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo