3
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Isn't the identity $u_n = a F_n + (b-a)F_{n-1}$ enough for your purposes? $\endgroup$ – Jack D'Aurizio Sep 21 '15 at 13:29
  • $\begingroup$ The person I am helping hasn't started undergraduate level maths yet (and is two years off), he learnt radians last week and has only just started differentiation and integration to give you a feel of the level they're at. I think something much simpler is required. I hadn't actually seen the identity before so thanks for your contribution anyway! $\endgroup$ – HBeel Sep 21 '15 at 13:33
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I could of never of thought of this, thankyou very much! $\endgroup$ – HBeel Sep 21 '15 at 18:42
  • $\begingroup$ @HBeel: You’re very welcome. $\endgroup$ – Brian M. Scott Sep 21 '15 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.