Pagina 1 di 1

Fatto noto sui Fibonacci

Inviato: 01 set 2014, 13:51
da <enigma>
Un esercizio semplice sui numeri di Fibonacci che torna utile aver visto almeno una volta nella vita. Dimostrare che per ogni intero fissato $k$, $F_{kn}$ è esprimibile come polinomio in $F_n$ e $F_{n-1}$. E se invece considero $F_{kn+l}$, con anche $l$ fissato?

Re: Fatto noto sui Fibonacci

Inviato: 01 set 2014, 18:53
da fph
Intendi "per ogni $k$ esiste un polinomio $p\in\mathbb{Z}[x,y]$ tale che per ogni $n$ si ha $F_{kn}=p(F_n,F_{n-1})$? Altrimenti se i quantificatori non son messi così nulla mi impedisce di prendere il polinomio costante uguale a $F_{kn}$...

Re: Fatto noto sui Fibonacci

Inviato: 01 set 2014, 21:24
da <enigma>
Sì.

Re: Fatto noto sui Fibonacci

Inviato: 07 set 2014, 11:44
da spugna
Si può dimostrare per induzione su $k$

Base: per $k=1$ ho che $F_{n+1}=F_{n-1}+F_n \Rightarrow F_{n+2}=F_{n-1}+2F_n \Rightarrow F_{n+3}=2F_{n-1}+3F_n \Rightarrow ...$

e in generale $F_{n+l}=F_lF_{n-1}+F_{l+1}F_n$ (1)(viene facilmente per induzione), per cui il polinomio cercato è

$p_{1,l}(x,y)=F_lx+F_{l+1}y$

Passo induttivo: suppongo che per un certo $k$ e per ogni $l$ esista $p_{k,l}$: allora, riprendendo la (1)

$F_{(k+1)n+l}=F_{n+(kn+l)}=F_{kn+l}F_{n-1}+F_{kn+l+1}F_n \Rightarrow p_{k+1,l}(x,y)=p_{k,l}(x,y)x+p_{k,l+1}(x,y)y$, che è ancora un polinomio