Solve a recurrence relation for a bit string of length n that starts with 1

Question

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!

Answer 1

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

Note that you might come up with other correct recurrence relations. The exact solution is

$ a(n)=2\cdot a(n-1) = \dots = 2^{n-1}\cdot a(1) = 2 ^ {n-1} $.