The Standard Bank IT Challenge (SBITC) is an annual coding competition for undergraduate and honours students in South Africa. The contest consists of two rounds: a regional event named the “heats”, and the final. In the heats, teams of up to four students each compete against other teams from the same university, and the winning team from each of the nine top-performing universities is invited to the final round in Johannesburg. Each member of the winning team wins a prize, and the winning university receives a large cash prize, but students mostly participate for the enjoyment that is to be obtained in solving the problems, and to test their skills against a set of problems that is designed to challenge the participants.

This year, the final problem from the heats (which took place on Saturday, 16 May) was fairly mathematical in nature; or more-so than the other problems at least. Essentially, the problem asks the following:

We consider generalised Fibonacci sequences $T_n$ which satisfy the same recurrence relation $T_{n + 2} = T_{n + 1} + T_n$ as the Fibonacci numbers, but with the first two terms $T_1$ and $T_2$ being arbitrary positive integers.

Now for some positive integer $N$, we can ask if $N$ will occur in such a sequence. The answer is yes, since one could consider any sequence where $T_1 = N$. Less trivially, one could consider the sequence where $T_1 = \lceil\frac{N}{2}\rceil$ and $T_2 = \lfloor\frac{N}{2}\rfloor$. The problem from the heats asks for the values of $T_1$ and $T_2$ for which $N$ occurs as late in the corresponding sequence as possible. If there is a tie between two sequences which contain $N$, then we choose the sequence for which $T_1$ is as small as possible.

Problems in coding contests usually have a story attached to them to make the problem statement more interesting. In this case, the problem was framed in terms of an archaeological expedition which sought to understand an ancient peoples to whom Fibonacci-like sequences were culturally significant. I have—however—lost my copy of the problems, and so am not able to provide the problem statement as it was given in the competition. I can provide a solution, however.

A good start to the problem would be to try to see what terms in these general Fibonacci-like sequence look like. If we start experimenting by calculating the first few terms, we see that
$T_3 = T_1 + T_2$
$T_4 = T_3 + T_2 = T_1 + 2T_2$
$T_5 = T_4 + T_3 = 2T_1 + 3T_2$
$T_6 = T_5 + T_4 = 3T_1 + 5T_2$
and we recognise the coefficients of $T_1$ and $T_2$ as the standard Fibonacci numbers $F_n$ given by $F_1 = F_2 = 1$ and $F_{n + 2} = F_{n + 1} + F_n$ for $n \geq 1$. We may conjecture that $T_{n + 2} = F_n T_1 + F_{n + 1} T_2$ for all $n \geq 1$. This is indeed true, and can be proven by using mathematical induction.

The statement that $N$ occurs in such a sequence then becomes
$F_n T_1 + F_{n + 1} T_2 = N$ for some positive integer $n$.
(We saw above that we can always make sure that $N$ is at least the third term in the sequence, and so we do not lose any generality by only considering $T_{n + 2} = N$ for positive $n$)

This suggests a method for trying to tackle the problem. We could consider all pairs $(F_n, F_{n +1})$ of Fibonacci numbers which are below $N$, and attempt solve the corresponding equation for $T_1$ and $T_2$. If we find a solution for which $T_1$ and $T_2$ are positive integers, then $N$ occurs at position $n + 2$ in the corresponding sequence. We then simply find the largest $n$ for which a solution exists, and use the solution $(T_1, T_2)$ for which $T_1$ is as small as possible. (In accordance with the problem specification) Since Fibonacci numbers grow exponentially, the number of pairs which we have to consider is logarithmic in $N$, and so this solution is feasible provided that we can efficiently solve the equation $F_n T_1 + F_{n + 1} T_2 = N$ for $T_1$ and $T_2$.

Such equations for which we seek integer solutions are known as Diophantine equations, after Diophantus of Alexandria. While it is known that there is no general algorithm for solving general Diophantine equations, and no algorithm for even determining whether an arbitrary Diophantine equation has a solution, solutions are known for many special cases.  In particular, there is a method for finding all solutions of linear Diophantine equations of the form $am + bn = c$, where $a$, $b$ and $c$ are known integers, and $m$ and $n$ are integers which are to be determined. This is exactly the form of the equation which we wish to solve, and I shall outline the method for finding all possible solutions below.

The first question which one may ask is: “When does the equation $am + bn = c$ have integer solutions?”. Clearly, if $(m, n)$ is a solution, then the greatest common divisor of $a$ and $b$ must be a factor of $c$. Is the converse true? If $\gcd(a, b)$ divides $c$, then does the equation necessarily have a solution in integers? The answer is yes. To prove this, we will make use of the following lemma:

Bézout’s Lemma: If $a$ and $b$ are any integers, then there exist integers $s$ and $t$ such that $as + bt = \gcd(a, b)$.

This is often proven by considering the set of all positive integers of the form $as + bt$, and showing that the smallest of them must be a divisor of both $a$ and $b$. A proof that is more useful if we wish to find the integers $s$ and $t$ is based on Euclid’s Algorithm for finding the greatest common divisor of two elements. I shall prove the following:
Suppose that $a$ and $b$ are positive integers, each at most $k$. Then there exist integers $s$ and $t$ such that $as + bt = \gcd(a, b)$.
This is clearly true for $k = 1$, since the only possibility is $\gcd(1, 1) = 1\cdot 1 + 1\cdot 0$. Now suppose that this holds for some $k$. We will show that it is also true for $k + 1$ as follows: Suppose $a$ and $b$ are positive integers, each at most $k + 1$. If $a = b$, then $\gcd(a, b) = a = a \cdot 1 + b \cdot 0$. Otherwise, suppose without loss of generality that $k + 1 \geq a > b$. Then $\gcd(a, b) = \gcd(b, a - b) = s_1 b + t_1 (a - b)$ for some integers $s_1$ and $t_1$, and we can take $s = t_1$ and $t = s_1 - t_1$.

The general case (where $a$ and $b$ need not be positive) follows by noting that $\gcd(a, b) = \gcd(-a, b) = \gcd(a, -b) = \gcd(-a, -b)$.
The proof above shows not only that the integers $s$ and $t$ exist, but provides a method for finding them recursively: first find the values of $s$ and $t$ for $(b, a - b)$, and use them to calculate the values of $s$ and $t$ for $(a, b)$ (if $a > b$. The case $b > a$ is similar). The base case for the recursion is $\gcd(a, 0)=1\cdot a+0\cdot 0$.

Many results about divisibility of numbers rely on Bézout’s Lemma. I will not prove these results, but will freely make use of them.

We now return to the question of whether the equation $am + bn = c$ has integer solutions if $\gcd(a, b) \mid c$. Let $c = k\gcd(a, b)$. By Bézout’s Lemma, we can find integers $s$ and $t$ such that $as + bt = \gcd(a, b)$. If we take $m = ks$ and $n = kt$, then $am + bn = k\gcd(a, b) = c$, and so we have found a solution. The question now becomes “How does one find all possible solutions?”

Suppose that $(m_1, n_1)$ is any solution to the equation, and that $(m, n)$ is some other solution. Let $p = n - n_1$. Then $am_1 + bn_1 = am + b(n_1 + p)$, and so $bp = a(m_1 - m)$. Thus $a \mid bp$ and so $\frac{a}{d} \mid p$ where $d = \gcd(a, b)$. Let $p = \frac{ak}{d}$. Then $\frac{bk}{d} = m_1 - m$, and so $m = m_1 - \frac{bk}{d}$. We see that the most general possible solution to the equation is $a(m_1 - \frac{bk}{d}) + b(n_1 + \frac{ak}{d}) = c$ where $d = \gcd(a, b)$, $k$ is any integer, and $(m_1, n_1)$ is any particular solution.

We now have all of the machinery which is needed to solve the problem. However, there are a few more results which greatly simplify the actual calculations which need to be performed.

Note that to find the general solution to $F_n T_1 + F_{n+1} T_2 = N$, we need to know the value of $d = \gcd(F_n, F_{n + 1})$. It is well known that the Fibonacci numbers possess the remarkable property that $\gcd(F_m, F_n) = F_{\gcd(m, n)}$. We do not need the general case here, but only that $\gcd(F_n, F_{n+1})=1$, which can easily be proved by induction.

We see that the equation  $F_n T_1 + F_{n+1} T_2 = N$ always has a solution, and that the general solution is given by
$T_1 = sN - F_{n + 1} k$ and
$T_2 = tN + F_n k$ where
$(s, t)$ is any solution to $sF_n + tF_{n + 1} = 1$, and $k$ is an arbitrary integer.

We are interested in the cases where $T_1$ and $T_2$ are positive, and also in the smallest possible value for $T_1$. The largest value of $k$ for which $T_1$ is positive is $k = \lceil\frac{sN}{F_{n+1}}\rceil-1$. This follows from noting that
$sN-F_{n+1}k>0$
$\iff k < \frac{sN}{F_{n+1}}$
$\iff k < \lceil\frac{sN}{F_{n+1}}\rceil$
$\iff k \leq \lceil\frac{sN}{F_{n+1}}\rceil-1$
This also gives us the smallest possible positive value of $T_1$ since $T_1$ is a decreasing function of $k$. If this value for $k$ does not make $T_2$ positive, then we see that it is impossible for $T_1$ and $T_2$ to be simultaneously positive ($T_2$ is an increasing function of $k$), and so there is no solution. Otherwise, we can use the solution corresponding to this value of  $k$.

We can now solve the original problem as follows:

• Loop over the pairs of Fibonacci numbers $(F_n, F_{n + 1})$ for which $F_{n + 1} < N$.
• For each pair, find integers $s$ and $t$ such that $sF_n + tF_{n + 1} = 1$ using the algorithm from Bézout’s Lemma above.
• Let $k = \lceil\frac{sN}{F_{n + 1}}\rceil - 1$.
• Let $T_1 = sN - F_{n + 1} k$ and $T_2 = tN + F_n k$. If $T_1$ and $T_2$ are positive, then store these values, along with $n$.
• Output the values of $T_1$ and $T_2$ that correspond to the largest value of $n$ for which these values were positive.

This is the solution which we submitted. It was accepted, and ran in time, but we can make a few improvements. When calculating the integers $s$ and $t$ such that $sF_{n}+tF_{n+1}=1$, for example, it is not necessary for the recursion to run to the base case. If $(s, t)$ are the required integers for $(F_{n - 1}, F_n)$ (which we have already computed), then the integers for the pair $(F_n, F_{n + 1})$ are $(t - s, s)$.

It is also possible to find the required integers $s$ and $t$ explicitly. Cassini’s Identity tells us that $F_{n + 1}F_{n - 1} - F_n^2 = (-1)^n$, so that one possible solution is $s = -F_n$ and $t = F_{n - 1}$ if $n$ is even, and $s = F_n$ and $t = -F_{n - 1}$ if $n$ is odd.

We can prove Cassini’s Identity directly using induction, of course, but could also use the fact that if
$A = \begin{pmatrix} 1&1\\ 1&0\end{pmatrix}$
then
$A^n = \begin{pmatrix} F_{n + 1} & F_n \\ F_n & F_{n - 1} \end{pmatrix}$
This can be proven using induction. (There’s no avoiding it) If we accept that this identity is true, then Cassini’s Identity follows by noting that
$F_{n+1}F_{n-1}-F_n^2=\det(A^n)=(\det(A))^n=(-1)^n$

This matrix representation of the Fibonacci numbers also allows us to prove other identities relating to the Fibonacci numbers. For example
$A^{m+n}=A^mA^n$ gives us that

$\begin{pmatrix}F_{m+n+1}&F_{m+n}\\F_{m+n}&F_{m+n-1}\end{pmatrix} =\begin{pmatrix}F_{m+1}&F_{m}\\F_{m}&F_{m-1}\end{pmatrix}\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}$
and so
$F_{m+n}=F_{m+1}F_{n}+F_mF_{n-1}=F_{n+1}F_{m}+F_nF_{m-1}$.

We could use this to prove the claim from earlier that $\gcd(F_m, F_n)=F_{\gcd(m, n)}$. The key idea is to show that $\gcd(F_{m+n}, F_m)=\gcd(F_n, F_m)$. Calculating the greatest common divisor of two Fibonacci numbers then becomes equivalent to applying Euclid’s Algorithm to their indices in the sequence. The proof makes use of the addition formula obtained above, and the fact that $\gcd(F_n, F_{n+1})=1$ which we also made use of earlier. Given these results, one obtains $\gcd(F_{m+n}, F_m)=\gcd(F_{m+1}F_n+F_mF_{n-1}, F_m)=\gcd(F_{m+1}F_n, F_m)=\gcd(F_n, F_m)$, where the last equality holds because $\gcd(F_{m+1}, F_m)=1$.

There is a wealth of other identities which can be discovered about the Fibonacci numbers, but they become increasingly less relevant to the SBITC problem. I will not present any further properties of the numbers here, but I do encourage you to experiment on your own and to see what you can discover.

 How clear is this post?