# Oxford and Cambridge Maths interview question – Fibonacci?

More Posts by Ronald | |
---|---|

*This is copied from my old blog (2023), for students applying to universities.*

I'm doing a lot of Mathematics and Computer Science mock interview questions right now. Here's a tricky example question that leads to an interesting discussion:

**Suppose a self-replicating machine has been invented. Every pair of self-replicating machines will produce one new self-replicating machines each day, indefinitely.**

So, start on Day 1 with 2 self-replicating machines. These work together and take one day to make a new machine.

On Day 2, we have 3 self-replicating machines. The original two self-replicating machines keep working, but the third self-replicating machine has to wait for a pal.

One Day 3, we have 4 self-replicating machines. Now we have two pairs, so they work together to make two new machines.

On Day 4, we have 6 self-replicating machines. And so on.

**Now for the question. Start out by showing your understanding, then face some hard questions. It's normal that you'll get hints to point you in the right direction - do use the comments if you need help:**

**a) How many self-replicating machines will we have on Day 10?**

**On Day 21, there will be 5395 machines. How many on Day 20?**

b) Now let be the number of machines on Day n, so .

**Can you suggest an upper bound for in terms of n?**

c) A *recurrence relation* for the Fibonacci sequence might look like:

,

for

**Write a recurrence relation for . Why is your recurrence relation correct?**

Feel free to comment for some discussion.

*Would you like to do some interview practice with me for Computer Science and Mathematics for Oxford, Cambridge and other university courses? Get in touch to arrange some sessions online: ronald@mathswithronald.com, WhatsApp +31682589013*