Pagina 1 di 2
153. disuguaglianza con fibonacci
Inviato: 19 ago 2013, 21:19
da jordan
Own (mix di fatti noti). Per ogni intero positivo n sia d(n) il numero di divisori di n e $f_n$ l'n-esimo numero di fibonacci. Dimostrare che
\[ d\left(\frac{f_1^2+f_2^2+...+f_n^2}{f_n}\right) \ge d(n+1)-1 \]
Re: 153. disuguaglianza con fibonacci
Inviato: 19 ago 2013, 21:44
da dario2994
$ d\left(\frac{f_1^2+f_2^2+f_3^2}{f_3}\right)=d\left(\frac{1^2+1^2+2^2}{2}\right)=d(3)=2<3=d(3+1) $
Re: 153. disuguaglianza con fibonacci
Inviato: 19 ago 2013, 22:33
da Lasker
Per prima cosa dimostro per induzione il lemma (in realtà fatto noto) sulla somma dei quadrati dei numeri di Fibonacci:
Lemma quadrati:$\sum_{k=1}^n {F_k}^2=F_nF_{n+1}$
1) Per $n=1$ è banalmente verificato
2)Passo induttivo:
$$\sum_{k=1}^n {F_k^2}+F_{n+1}^2=F_nF_{n+1}+F_{n+1}^2$$
$$\sum_{k=1}^{n+1} {F_k^2}=F_{n+1}(F_n+F_{n+1})$$
Per definizione dei numeri di Fibonacci vale $F_n+F_{n+1}=F_{n+2}$, dunque il lemma si può dire dimostrato

.
Ora, sostituisco la relazione del "
Lemma quadrati" nella disuguaglianza di partenza, ottenendo:
$$d\left(F_{n+1}\right)\geq d(n+1)-1$$
Per concludere, mi servo del seguente teorema:
Teorema di "divisibilità":se $r\mid s $, allora $F_r\mid F_s$
Dunque, se $n+1$ ha come divisori $(a_1,a_2,...,a_i)$, allora $F_{n+1}$ ha sicuramente come divisori $(F_{a_1},...,F_{a_i})$, che sono tutti diversi, a parte il caso particolare $F_1=F_2=1$.
Dunque ne posso sempre trovare almeno $d(n+1)-1$, che è proprio la tesi.
EDIT:ho cambiato la parte confusionaria in cui pretendevo di aver dimostrato una cosa falsa

Re: 153. disuguaglianza con fibonacci
Inviato: 19 ago 2013, 22:37
da Triarii
Beh veramente il tuo metodo credo non funzioni ogni volta che hai $ f_a $ con $ a $ pari, visto che stai considerando anche $ f_2=f_1=1 $ come divisori, e non solo in quel caso. Dovresti trovare un altro divisore.
Re: 153. disuguaglianza con fibonacci
Inviato: 19 ago 2013, 23:15
da jordan
No, triari, quel -1 c'e' apposta.
[edit]
Re: 153. disuguaglianza con fibonacci
Inviato: 19 ago 2013, 23:18
da Triarii
Non avevo visto che avevi editato sorry
Re: 153. disuguaglianza con fibonacci
Inviato: 20 ago 2013, 01:10
da jordan
Lasker, non hai fortemente imbrogliato: prova prima a mostrare che \[ f_{a+b}=f_{a-1}f_b+f_af_{b+1}\] e poi vedi come questo implica ciò che ti serve..
Re: 153. disuguaglianza con fibonacci
Inviato: 20 ago 2013, 10:04
da Lasker
Ok, faccio il tentativo!
$$F_{a+b}=F_{a-1}F_{b}+F_{a}F_{b+1}$$
Ora vado di induzione su $b$
1)Passo base:$b=1$ (due casi base, $b=F_1$ e $b=F_2$)
$F_{a+1}=F_{a-1}+F_{a}$, che è vero per definizione dei numeri di Fibonacci.
2)Passo induttivo:
$F_{a+b}+F_{a+b-1}=(F_{a-1}F_{b}+F_{a}F_{b+1})+(F_{a-1}F_{b-1}+F_{a}F_{b})$
$ F_{a+b+1}=F_{a}(F_b+F_{b+1})+F_{a-1}(F_b+F_{b-1})$
Sostituendo nelle parentesi, ottengo:
$F_{a+b+1}=F_{a-1}F_{b+1}+F_{a}F_{b+2}$, che è la tesi.
A questo punto, provo a dimostrare il mistico "teorema di divisibilità":
Procedo usando la relazione precedente, per dimostrare che $r\mid {r+s} \Rightarrow F_r\mid F_{r+s}$ per ogni $s,r$.
$F_{r+s}=F_{r-1}F_{s}+F_{r}F_{s+1}=F_r(k_1F_{r-1}+F_{s+1})$
Da cui, $r\mid r+s$ è condizione sufficiente per la quale $F_r\mid F_{r+s}$.
Dunque dovrei aver concluso la dimostrazione (si spera

)
Re: 153. disuguaglianza con fibonacci
Inviato: 20 ago 2013, 10:48
da jordan
Apposto, vai col prossimo
Re: 153. disuguaglianza con fibonacci
Inviato: 21 ago 2013, 18:20
da Drago96
Io invece "imbroglio" davvero e dico che
$$\displaystyle d(F_n)\ge2^{\Omega(n) }$$
Dove $\displaystyle\Omega\left(p_1^{\alpha_1}\cdots p_k^{\alpha_k}\right):=\alpha_1+\dots+\alpha_k$
In realtà ci vorrebbe un $-1$ all'esponente in alcuni (infiniti

) casi, ma sono piuttosto sicuro che si possa omettere tranne che con $n=4$...
Re: 153. disuguaglianza con fibonacci
Inviato: 22 ago 2013, 10:42
da jordan
come lo dimostri?
Re: 153. disuguaglianza con fibonacci
Inviato: 22 ago 2013, 10:51
da <enigma>
jordan ha scritto:come lo dimostri?
Io ho usato $F_k|F_{kn}$+il
teorema di Carmichael
Re: 153. disuguaglianza con fibonacci
Inviato: 22 ago 2013, 11:17
da Drago96
Esatto!

Io l'avevo fatto spezzando sulle potenze di primi (ovvero scrivendo $\displaystyle F(p_1^{\alpha_1}\cdots p_k^{\alpha_k})=h\cdot F(p_1^{\alpha_1})\cdots F(p_k^{\alpha_k})$ ) e poi mostrando il fatto sulle potenze dei primi e usando il fatto sul gcd... però mi accorgo che in effetti basta continuare a togliere primi e quindi divisori primitivi... xD
Tra l'altro alla pagina di wiki c'è anche un link ad una dimostrazione che mi pare del tutto elementare...
EDIT: vorrei anche fare notare a Lasker che il lemma dei quadrati ha anche una bella interpretazione geometrica, ovvero nientemeno che la costruzione della spirale aurea!

Re: 153. disuguaglianza con fibonacci
Inviato: 22 ago 2013, 17:40
da jordan
Uh, figo, non lo conoscevo! Sa molto di generalizzazione di Zsigmondy per classi di sequenze $(a_n)_{n \in \mathbb{N}_0}$ della forma $a_{n+2}=\alpha a_{n+1}+\beta a_n$. Per la disuguaglianza di sopra, direi che hai considerato solo divisori della forma $f_d$ con $\omega(d)=1$, ma dimenticato le 3 eccezioni del teorema, e dovrebbe quindi essere della forma $\sigma_0(f_n) \ge 2^{\Omega(n)-4}$

Il fatto che $(f_n)_{n \in \mathbb{N}_0}$ è una sequenza di Mersenne non mi pare sia utilizzato (premesso che non conosco la dimostrazione del teorema di Carmichael); l'insieme degli $f_d$ con $d\mid n$ è un sottoinsieme dell'insieme dei divisori di $f_n$. Bene, mettiamoli in ordine crescente. Nel caso peggiore $n$ è pari, cosicchè $f_1=f_2=1$ e questo sottoinsieme dei divisori di $f_n$ avrà almeno $\sigma_0(n)-1$ elementi distinti. Tra questi ultimi, apparte le tre eccezioni dei teorema di sopra, esiste sempre un divisore primitivo. Questo mostra che, nel caso peggiore, il numero di fattori di $f_n$ (con $n\ge 12$) verifica $\omega(f_n) \ge \sigma_0(n)-4$. A sua volta, implica \[ \sigma_0(f_n) \ge 2^{\sigma_0(n)-4} \ge 2^{2^{\omega(n)}-4}, \]
che è piu' forte di quella di sopra. Ho fallato da qualche parte?
Re: 153. disuguaglianza con fibonacci
Inviato: 22 ago 2013, 21:36
da Drago96
Woo! Sì, direi che il tuo bound funziona e surclassa il mio!

Io infatti considero solo roba coprima (Fibonacci delle potenze dei primi) mentre in realtà ogni divisore porta un nuovo fattore!
Ah, nel mio non devo considerare le eccezioni perché non sono potenze di primi, e io come ho detto prima scompongo in prodotto di Fibonacci di potenze di primi per spezzare la funzione dei divisori e con l'induzione dire che $\sigma_0(F_{p^k})\ge2^k$ tranne nel caso del 2, in cui ci va appunto il -1...
P.S: mi scuso se è poco chiaro, ma dal telefono non sono troppo comodo a scrivere con LaTeX...
