Successione dei numeri di Fibonacci e Induzione
Esercizio proposto:
Sia $ {F_{n} : n in N} $ la successione dei numeri di Fibonacci,
$ { ( F_{1}= F_{2} = 1 ),( F_{n} = F_{n-1} + F_{n-2}):} $
per $ n >= 3 $
Dimostrare per induzione che $ sum_(i = 1) F_{i}^2 = F_{n}F_{n+1} $ , per ogni $ n >= 1 $
Il mio dubbio sulla prima parte è quel $ n >= 3 $ , nel senso, io la successione di Fibonacci l'ho sempre trovata scritta con $ n >= 2 $ . Ho ho risolto la successione come una normale successione, anche se non sono sicura se vada bene considerato il $ n >= 3 $ .
Il vero problema arriva con l'induzione, in cui non so proprio da dove partire. Devo usare la successione di Fibonacci svolta prima? È un altro esercizio? Come si svolge?
Sia $ {F_{n} : n in N} $ la successione dei numeri di Fibonacci,
$ { ( F_{1}= F_{2} = 1 ),( F_{n} = F_{n-1} + F_{n-2}):} $
per $ n >= 3 $
Dimostrare per induzione che $ sum_(i = 1) F_{i}^2 = F_{n}F_{n+1} $ , per ogni $ n >= 1 $
Il mio dubbio sulla prima parte è quel $ n >= 3 $ , nel senso, io la successione di Fibonacci l'ho sempre trovata scritta con $ n >= 2 $ . Ho ho risolto la successione come una normale successione, anche se non sono sicura se vada bene considerato il $ n >= 3 $ .
Il vero problema arriva con l'induzione, in cui non so proprio da dove partire. Devo usare la successione di Fibonacci svolta prima? È un altro esercizio? Come si svolge?
Risposte
Secondo me ti stai troppo focalizzando sul nome delle cose. Come risolveresti l'esercizio di quel tipo se fosse la prima volta che senti parlare di Fibonacci? Non serve alcuna conoscenza al di fuori del testo del problema.
Comunque devi procedere per induzione, quindi supponi la tesi valga per un qualche valore e dimostrala per il successivo. E non dimenticarti del caso base.
Comunque devi procedere per induzione, quindi supponi la tesi valga per un qualche valore e dimostrala per il successivo. E non dimenticarti del caso base.
Ci ho provato/pensato, ma non ho mai visto un'induzione scritta così, non so neanche come procedere per la base induttiva
Usi che \(\sum_{i=1}^{N+1}F_{i}^2=F_{N+1}^2+\sum_{i=1}^{N}F_{i}^2\) e continui usando la tesi su \(F_N\).
Base:
P(1) : $ F_{i}^2 = 1 $ e $ F_{n}F_{n+1} = 1 * 1 = 1 $
e quindi P(n) è vera.
Passo induttivo:
P(n+1):
$ sum_(i = 1)^(n+1) F_{i}^2 = sum_(i=1)^(n)F_{i}^2 + F_{n+1}^2 $
$ sum_(i = 1)^(n+1) F_{i}^2 = F_{n}F_{n+1} + F_{n+1}^2 $
$ = F_{n+1}F_{n+2} $
e quindi visto che P(n+1):
$ sum_(i = 1)^(n+1) F_{i}^2 = F_{n+1}F_{n+2} $
è dimostrato P(n+1).
è giusta così?
P(1) : $ F_{i}^2 = 1 $ e $ F_{n}F_{n+1} = 1 * 1 = 1 $
e quindi P(n) è vera.
Passo induttivo:
P(n+1):
$ sum_(i = 1)^(n+1) F_{i}^2 = sum_(i=1)^(n)F_{i}^2 + F_{n+1}^2 $
$ sum_(i = 1)^(n+1) F_{i}^2 = F_{n}F_{n+1} + F_{n+1}^2 $
$ = F_{n+1}F_{n+2} $
e quindi visto che P(n+1):
$ sum_(i = 1)^(n+1) F_{i}^2 = F_{n+1}F_{n+2} $
è dimostrato P(n+1).
è giusta così?
Sì, sugli appunti magari mostra il passaggio in cui raccogli il fattore comune. Puoi anche osservare che per \(N=1\) utilizzi la definizione ricorsiva per \(N+2=3\) quindi la formula è effettivamente valida.
Scusa, non sono sicura di aver capito..
Per quanto riguarda il tuo primo dubbio, quello riguardante \( n \ge 3 \) laddove tu ricordavi \( n \ge 2 \), la cosa è molto semplice. Chi ha preparato l'esercizio assume che sia \( 0 \notin \mathbb{N} \): se fosse \( n \ge 2 \) avresti che \( F_{2} = F_{1} + F_{0} \) con \( F_{0} \) non solo non definito ma nemmeno definibile, essendo \( 0 \notin \mathbb{N} \). Qualora fosse stato \( 0 \in \mathbb{N} \), avrebbe avuto senso \( n \ge 2 \) ma a patto di definire \( F_{0} \) che di solito è definito con la posizione \( F_{0} = 0 \), sicché la successione di Fibonacci risulta ricorsivamente definita da:
\[
F_{n} =
\begin{cases}
0 & \text{ se } n = 0 \\
1 & \text{ se } n = 1 \\
F_{n-1} + F_{n-2} & \text{ se } n \ge 2
\end{cases}
\]
Nota che in questo caso la successione di Fibonacci anziché iniziare con \( 1 \) sarebbe iniziata con \( 0 \), per poi proseguire normalmente.
P.S.
Prima ho detto "di solito" perché si potrebbe anche porre ancora una volta \( F_{0} = F_{1} = 1 \), facendo cioè ancora iniziare la successione di Fibonacci con \( 1 \), che suonerebbe però come un piccolo spreco visto che essendo \( 0 \in \mathbb{N} \) possiamo anche farla iniziare con \( 0 \).
P.P.S.
Una piccola nota. Il fatto che \( \mathscr{P}(1) \) sia vera non significa che \( \mathscr{P}(n) \) è vera. Significa che \( \mathscr{P}(1) \) è vera.
\[
F_{n} =
\begin{cases}
0 & \text{ se } n = 0 \\
1 & \text{ se } n = 1 \\
F_{n-1} + F_{n-2} & \text{ se } n \ge 2
\end{cases}
\]
Nota che in questo caso la successione di Fibonacci anziché iniziare con \( 1 \) sarebbe iniziata con \( 0 \), per poi proseguire normalmente.
P.S.
Prima ho detto "di solito" perché si potrebbe anche porre ancora una volta \( F_{0} = F_{1} = 1 \), facendo cioè ancora iniziare la successione di Fibonacci con \( 1 \), che suonerebbe però come un piccolo spreco visto che essendo \( 0 \in \mathbb{N} \) possiamo anche farla iniziare con \( 0 \).
P.P.S.
Una piccola nota. Il fatto che \( \mathscr{P}(1) \) sia vera non significa che \( \mathscr{P}(n) \) è vera. Significa che \( \mathscr{P}(1) \) è vera.