0
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ $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$). $\endgroup$ – saulspatz Apr 17 '19 at 22:02
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.