# How to solve a recurrence relation for a bit string of length n that starts with 1?

I am doing a homework assignment and am stuck on the following problem: Find a recurrence relation and give initial conditions for the number of bit strings of length n begin with 1.

I'm not sure how to solve the problem, but I think that the initial condition of a(0) = 1. Thank you so much for any help!

• $a(0) =1$ would mean there is one bit string of length $0$ that starts with $1$. There is one string of length $0$, but it doesn't start with $1$ (or with $0$). – saulspatz Apr 17 '19 at 22:02

If you allow the string to start with a $$0$$, then there are as many strings of length $$n$$ that start with $$1$$ as there are starting with $$0$$, namely $$a(n)$$ many. So to build a string of length $$n+1$$ that starts with $$1$$, you can have a $$0$$ or a $$1$$ next. If you have a $$1$$ next, then you have $$a(n)$$ possibilities. If there is a $$0$$ next, then you also have $$a(n)$$ possibilities. Try solving it yourself from here. A recurrence relation is given by:
$$a(n+1)=2\cdot a(n)$$, and $$a(1)=1$$ (not $$a(0)=1$$).
$$a(n)=2\cdot a(n-1) = \dots = 2^{n-1}\cdot a(1) = 2 ^ {n-1}$$.