Σελίδα 1 από 1

ΜΚΔ όρων ακουλουθιών!

Δημοσιεύτηκε: Κυρ Ιουν 19, 2016 9:21 pm
από matha
Οι ακολουθίες \displaystyle{(a_n)_{n> 0},(b_n)_{n> 0}} ορίζονται από τη σχέση

\displaystyle{(1-\sqrt{5})^n=a_n-b_n\sqrt{5}.}

Βρείτε τον \displaystyle{\gcd (a_n,b_n).}

Re: ΜΚΔ όρων ακουλουθιών!

Δημοσιεύτηκε: Δευ Ιουν 20, 2016 3:53 am
από panos misiakos
Αρχικά παρατηρούμε ότι a_{1}=b_{1}=1
Επίσης a_{n+1}-b_{n+1}\sqrt{5}=(1-\sqrt{5})^n(1-\sqrt{5})=(a_{n}-b_{n}\sqrt{5})(1-\sqrt{5})
Δηλαδή θα έχουμε a_{n+1}=a_{n}+5b_{n} και b_{n+1}=b_{n}+a_{n}
Έτσι ,λοιπόν, λαμβάνουμε gcd(a_{n+1},b_{n+1})=gcd( a_{n}+5b_{n}, b_{n}+a_{n})=gcd(4b_{n},a_{n}+b_{n}) , το οποίο είναι ίσο με:
(Edit : Διόρθωση έπειτα από παρατήρηση του κ. Θάνου)
-4gcd(a_{n},b_{n}),αν \frac{a_{n}+b_{n}}{gcd(a_{n},b_{n})}\equiv 0 (mod 4)
-2gcd(a_{n},b_{n}),αν \frac{a_{n}+b_{n}}{gcd(a_{n},b_{n})}\equiv 2 (mod 4)
-gcd(a_{n},b_{n}),αν \frac{a_{n}+b_{n}}{gcd(a_{n},b_{n})}\equiv 1,3 (mod 4)

Επαγωγικά θα δείξουμε ότι η c_{n}=\frac{a_n+b_n}{gcd(a_n,b_n)} (mod 4) είναι ίση με
2, αν n\equiv 1mod3,
0, αν n\equiv 2mod3,
1,3, αν n\equiv 0mod3.
Πράγματι, έχουμε τις παρακάτω περιπτώσεις :
-Αν c_n\equiv 0 mod 4 τότε c_{n-1}\equiv 2 mod 4,c_{n-2}\equiv 1,3 mod 4 και c_{n+1}=\frac{a_{n+1}+b_{n+1}}{gcd(a_{n+1},b_{n+1})}=\frac{2a_n+6b_n}{4gcd(a_n,b_n)}=\frac{4a_{n-1}+8b_{n-1}}{4gcd(a_{n-1},b_{n-1})}=2+c_{n-2}\equiv 1,3 mod4
(Με όμοιο τρόπο προκύπτουν και οι λοιπές περιπτώσεις.)
Συνεπώς gcd(a_n,b_n)=2^{3\lfloor (n-1)/3 \rfloor+(n-1)mod 3}

Re: ΜΚΔ όρων ακουλουθιών!

Δημοσιεύτηκε: Δευ Ιουν 20, 2016 2:51 pm
από dement
panos misiakos έγραψε:=gcd(4b_{n},a_{n}+b_{n}) , το οποίο είναι ίσο με:
-4gcd(a_{n},b_{n}),αν a_{n}+b_{n}\equiv 0 (mod 4)
Πάνο, αυτό δεν ισχύει (πάρε, π.χ., a_n = 16, b_n = 8).