Let $u_{n+2} = u_{n+1} + u_n$ where $u_1 = a, u_2 = b$. How many pairs exists $(a,b)$ such that $u_k = 21$ for some $k$?

Question

A sequence of non negative integers $u_n$ is defined by $u_1 = a, u_2 = b$ and $u_{n+2} = u_{n+1} + u_n$. How many pairs of non-negative integers $(a,b)$ are there such that $21$ is a term of the sequence with $a \not = 21$ and $b \not = 21$?

The solution to this question is 40, however I was hoping there was a quicker solution to the question other than brute force.

I tried brute force two ways, one was to enumerate values (a,b) and check them, this was quite slow even with some subtle clues: I worked out if $(a,a)$ was a solution then so was $(a,0)$ and $(0,a)$ and that if you write out a sequence for some $(a,b)$ that has $21$ in it, then all pairs before $21$ will work.

I also tried another brute force method where I observed the sequence went $a,b,a+b,a+2b,2a+3b,3a+5b,5a+8b,8a+13b,13a+21b,21a+34b$ and then went through the terms and found solutions to the equation, faster but still slow.

This question is from a math competition and suspect both are too slow, a third solution I thought of was finding the closed form but this method is still quite slow (and too advanced for the person I am helping)

Does anyone have a solution for this, that would be suitable in a maths competition? I'm sure this is some sort of trick but I can't see it.

Source of question: Senior Team Maths Challenge 2014/15 regional final

Thanks

Answer 1

Here’s a completely elementary systematic method for finding all $40$ solutions without trial and error. The key is to work backwards from $21$. That is, if $u_n=21$, $u_{n-1}$ must be less than $21$, and it’s also easy to check that it cannot be $0$. Thus, $u_{n-1}$ must be one of the integers $1$ through $20$. Clearly $u_{n-2}=u_n-u_{n-1}$, $u_{n-3}=u_{n-1}-u_{n-2}$, and so on, so all earlier terms are completely determined by the first two. We stop working backwards when the next number would be negative. Thus, we get the following sequences:

$$\begin{align*} &21,20,1,19\\ &21,19,2,17\\ &21,18,3,15\\ &21,17,4,13\\ &21,16,5,11\\ &21,15,6,9\\ &21,14,7,7,0,7\\ &21,13,8,5,3,2,1,1,0,1\\ &21,12,9,3,6\\ &21,11,10,1,9\\ &21,10,11\\ &21,9,12\\ &21,8,13\\ &21,7,14\\ &21,6,15\\ &21,5,16\\ &21,4,17\\ &21,3,18\\ &21,2,19\\ &21,1,20 \end{align*}$$

In each sequence any number after the first two could be $u_1$, so there are

$$6\cdot2+4+8+2\cdot3+10=40$$

starting points and hence $40$ choice of $\langle a,b\rangle$.