MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 corrected the powers of two example from B = 2 to B = -2.

This might not be common, but I once believed the following.

Let $ A, B $ be integers, and define a sequence by the linear recurrence $ s_n = A s_{n-1} + B s_{n-2} $ with the base case $ s_0 = 0 $, $ s_1 = 1 $. Two important special cases are the Fibonacci sequence ($ A = B = 1 $) and the sequence $ s_n = 2^n - 1 $ (where $ A = 3 $, $ B = -2 $). Then, for any integers $ n $ and $ k $, $ \gcd(s_n, s_k) = s_{\gcd(n,k)} $.

This is true in the two mentioned special cases, so it's tempting to believe it's true in general. But there's a counterexample: $ A = B = k = 2 $, $ n = 3 $.

Update: corrected the powers of two minus one example from B = 2 to B = -2. Thanks to Harry Altman.
show/hide this revision's text 1 [made Community Wiki]

This might not be common, but I once believed the following.

Let $ A, B $ be integers, and define a sequence by the linear recurrence $ s_n = A s_{n-1} + B s_{n-2} $ with the base case $ s_0 = 0 $, $ s_1 = 1 $. Two important special cases are the Fibonacci sequence ($ A = B = 1 $) and the sequence $ s_n = 2^n - 1 $ (where $ A = 3 $, $ B = 2 $). Then, for any integers $ n $ and $ k $, $ \gcd(s_n, s_k) = s_{\gcd(n,k)} $.

This is true in the two mentioned special cases, so it's tempting to believe it's true in general. But there's a counterexample: $ A = B = k = 2 $, $ n = 3 $.