# Discrete Mathematics Recursion

A bacteria colony begins with $$6$$ individuals and doubles in size every hour. Write down a recurrence for a population at the beginning of hour n, and solve it. How many hours elapse until the population exceeds one million?

This is what I wrote: $$a_n=2a_{n-1}$$ for $$\forall n\ge 1$$ where our $$a_0=6$$ (sorry I don't know how to write it properly)

However the solution continues with : We know $$a_0 = 1$$, so: $$a_n = 2a_{n−1} = 2^2a_{n−2} = 2^3a_{n−3} = \cdots = 2^na_0 = 6\cdot 2^n$$. This is the part which I do not understand. Can someone explain it to me?

Thank you!

• I've edited it. Is that what you mean? – tarit goswami Apr 10 at 10:00
• I think the solution was supposed to continue with "We know $a_0 = 6$". – Arthur Apr 10 at 10:07
• tarit actually the solution was an = 2an−1 = 22an−1 = 23an−2 = ... = 2na0 = 6·2n. which may be wrong – Flea Apr 10 at 10:20

We know $$a_0=1$$
Here $$a_0=6$$. $$a_n=2a_{n-1}$$ is called recurrence relation, where $$n$$th term is related to $$(n-1)$$ th term by the given relation. Here $$n$$ is a variable which can take values $$\ge 1$$. Hence, we can also write $$a_{n-1}=2a_{n-2}$$ and $$a_{n-2}=2a_{n-3}$$ and so on upto $$a_1=2a_0$$(minimum value of $$n$$ can be $$1$$).
So, putting the values back, we can say, $$a_n=2a_{n-1}=2\cdot (2a_{n-2})=2^2a_{n-2}\\=2^2\cdot (2a_{n-3})=2^3a_{n-3}$$ and in general, $$a_n=2^ka_{n-k}$$ where $$1\le k\le n$$. So, finally you will have $$a_n= 2^na_0=6\cdot 2^n$$, as $$a_0=6$$. Have you understood now?