This is question 2 from the 1983 British Maths Olympaid
The fibonacci sequence $f_{n}$ is defined by $f_{1} = 1, f_{2} = 1,$ and $f_{n} = f_{n-1} + f_{n-2}, n > 2$
prove that there are integers a, b and m such that $0 < a < m$, $0 < b < m$ and $f_{n}-anb^{n}$ is divisible by $m$ for all positive integers $n$.
I'm pretty sure I've solved the question, but this is my first time solving a question like this with divisibility in sequences, so please could someone look at my solution and tell me places where there are better routes or improvements. I also think my solution is quite long for a question 2 problem, which makes me think there is an easier, quicker way that I have overlooked.
My solution:
By the inequality condition, we see $m = 1$ is impossible, then
let $T_{n} = f_{n} - anb^{n}$, so,
$m|T_{1}$ and $m|T_{2}$.
$m|1-ab$ -----> (A) from this we can also see m must not divide a or b, or else $m|1$ which means for $m>0$ we get $m = 1$ which is impossible
$m|1-2ab^{2}$ -----> (B)
multiply (A) by $2b$
$m|2b-2ab^{2}$ -----> (C)
$m|(C) - (A)$ so,
$m|2b-1$
$m|T_{1} + T_{2}$ and $m|T_{3}$, since these two parts have the same constant I thought to subtract one from the other and get an expression only in terms of $a$ and $b$ which I then factorised to get
$m|ab(b-1)(3b+1)$
since m doesn't divide a or b, $ab$ can be removed. Also, $m|2b-1$ but m doesn't divide $b$, so $m$ doesn't divide the difference between $2b-1$ and $b$. So, $m|b-1$ is impossible, meaning (b-1) can be removed too, leaving us with
$m|3b+1$ and $m|2b-1$ so
$m|6b+2$ and $m|6b-3$ so
$m|(6b+2) - (6b-3)$ so
$m|5$.
Under current restrictions for $m$ only $m=5$ is possible, so $m = 5$. $a<5, b<5$
for $T_{1} \equiv 0\pmod{5}$ it must be that $ab \equiv 1\pmod{5}$. The only possible pairs $(a,b)$ are $(1,1)$, $(4,4)$ and $(2,3)$ or $(3,2)$.
I just tested each pair for $T_{n}$ divisibility by $5$, where they all failed quite quickly except for $(a,b) = (2,3)$.
Now we just have to prove that this pair works. I decided to do this by having $S_{n} = 2(n)(3^{n})$ and showing that $S_{n} \equiv f_{n}\pmod{5}$ for all $n$. This I found I could do by showing $S_{n}$ follows the same relation as $f_{n}$ in$\mod{5}$ and has the same start terms (1 and 1).
We could have done this by calculating $f_{n}\pmod{5}$ for some time and eventually see that it becomes a repeating sequence, so we could just calculate $S_{n}\pmod{5}$ upto that point and show that $S_{n}\pmod{5}$ is also repeating with the same period as $f_{n}\pmod{5}$ and that all the terms are equal, but I wanted to avoid much computation and instead tried the following.
Now to show $S_{n} \equiv f_{n}\pmod{5}$ for all n:
We follow the route of showing that $S_{n} \pmod{5}$ follows the same relation as $f_{n}\pmod{5}$.
we know by applying $\pmod{5}$ to the fibonacci sequence definition, $f_{n} \equiv f_{n-1} + f_{n-2} \pmod{5}$. So, since we already have $S_{1} \equiv f_{1} \pmod{5} $ and $S_{2} \equiv f_{2} \pmod{5}$ by some calculations, we just need to show that
$S_{n} \equiv S_{n-1} + S_{n-2} \pmod{5}$.
base case:
$S_{3} \equiv S_{1} + S_{2}\pmod{5}$ which is true.
By definition,
$S_{k+1} = 2(k+1)(3^{k+1})$
$S_{k+1} = (2k+2)(3^{k+1})$
$S_{k+1} = (2k)(3^{k+1}) + 2(3^{k+1})$
$S_{k+1} = (2k)(3^{k})(3) + 2(3^{k+1})$
$S_{k+1} = (2k)(3^{k}) + 2((2k)(3^{k})) + 2(3^{k+1})$
$S_{k+1} = 2k(3^{k}) + (6)(2k)(3^{k-1}) + 2(9)(3^{k-1})$
Now since we are considering $S_{n} \pmod{5}$, I applied $\pmod{5}$ to the above equation.
$S_{k+1} \equiv 2k(3^{k}) + 2k(3^{k-1}) - 2(3^{k-1})\pmod{5}$
$S_{k+1} \equiv 2k(3^{k}) + 2(k-1)(3^{k-1})\pmod{5}$
$S_{k+1} \equiv S_{k} + S_{k-1}\pmod{5}$
This is the same recurrence relation as $f_{n}\pmod{5}$ and since they have the same starting two values, 1 and 1, $S_{n} \equiv f_{n} \pmod{5}$ for all $n$, meaning that
$f_{n} - S_{n} \equiv 0\pmod{5}$ for all $n$ ie:
$5|f_{n} - 2n(3^{n}) $ for all $n$, which means that $m =5$, $a = 2$ and $b = 3$ are the only positive integers with $a<m$ and $b<m$ that allow $m$ to divide every term of the sequence $T_{n}$.
Here's how I solved it.
The given problem can be formulated as: Prove that $f_n = anb^n$ mod $m$. I didn't want to think about whether various theorems hold over rings, so I'm going to initially hope that we can solve this with $m$ being prime. That way everything is over a field.
The solution to a recurrence of the form
$$af_{n} + bf_{n-1} + cf_{n-2} = 0$$
has a known general form. In particular, if the characteristic polynomial $ax^2 + bx + c$ has a double root $r$, the solution will be of the form $f_n = k_1r^n + k_2nr^n$. So we can hope that we can find $m$ so that $x^2 - x - 1$ has a double root mod m. Then, if we are really lucky, $k_1$ will be zero and we'll be done.
By the quadratic formula, the roots of $x^2 - x - 1$ are
$$2^{-1}(1 \pm \sqrt{5}).$$ To get a double root, we need the positive and negative square roots of 5 to be equal. Obviously this happens mod 5, where the root is 3. Now we just have to work out the values of $k_1$ and $k_2$, and very fortunately, we get $k_1 = 0$ and $k_2 = 2$, so the solution is $f_n = 2n3^n$ mod 5.
This method was clearly not guaranteed to work, but I hoped it might, and it did. If I were writing up the answer on an actual Olympiad, I would not waste time writing up how I came to the answer. Once I have the constants, all I need to do is prove that $f_n = 2n3^n$ mod 5, which is quite straightforward. I also did not prove that this is the only solution, but that's not actually part of the question.