Hello! I'm Ronald. I work online as a personal maths tutor 😃

I'm building this website for A-Level Maths students.
Some new content: Proof by Induction

# Oxford and Cambridge Maths interview question – Fibonacci?

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 ${\displaystyle S_{n}}$ be the number of machines on Day n, so ${\displaystyle S_{1}=2}$.

Can you suggest an upper bound for ${\displaystyle S_{n}}$ in terms of n?

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

${\displaystyle F_{1}=1,F_{2}=1}$,

${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$ for ${\displaystyle n>2}$

Write a recurrence relation for ${\displaystyle S_{n}}$. 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