## Section 5.1

5. (a)-(c): a_n=3*a_(n-1) and a_0=2
Just do this: a_n = 3a_(n-1)=3( 3a_(n-2))=3^2 3a_(n-3) = ... = 3^n a_(n-n)

a_n=a_(n-1) + 2, a_0 =3
Similarly: a_n = a_(n-1)+2 = (a_(n-2)+2) + 2 = a_(n-3) + 3*2 = ... = a_(n-n) + n*2

a_n=a_(n-1)+n, a_0=1
a_n=a_(n-1)+n = ( a_(n-1) + (n-1) ) + n = a_(n-1) + ( n+(n-1) ) = a_(n-2) + ( n+(n-1)+(n-2)) = ... = a_(n-n) + (n+(n-1)+ ... + (n-n) = a_0 + (1/2)n*(n+1)

9. n cars made in nth month. How many by the end of the nth month, first year, solve for explicit nth month formula.

C_n = number of cars by the end of the nth month. C_n=C_(n-1)+n. We already solved a_n = a_(n-1)+n in Question 5. So C_n = C_0 + (1/2) n*(n+1). Of course, we can't depend on Question 5 for the initial condition, but we are told that 1 car in the first month, so C_0=0 (i.e. C_1=1). Of course C_(12)=(1/2)*(12)(13)=6*13=78. 13. \$1 coin, \$1 bill, or \$5 bill. Number of ways to depost \$n. Initial conditions, How many for \$10.

Let us say the d_n is the number of ways of depositing \$n. d_0=1, d_1=2 (either of the \$1 legal tenders). Whether or not we have to specify d_2 (or more) depends on the recurrence relation we obtain.

Indeed, if we are to deposit \$n and we decide to start with a \$5 bill this would only hold if n>4. So for n>4, d_n = d_(n-5) + 2*d_(n-1). Either start with a \$5 or with one of the two types of \$1's and then continue with how much you still owe, either \$(n-5) or \$(n-1).
So we must specify d_2, d_3, d_4. Actually these satisfy their own recurrence relation: d_j = 2*d_(j-1) since we can pretend we don't have any \$5 till we get to n=5. Hence d_2=4, d_3=8, d_4=16.

To find d_(10), continue to find: d_5 = d_0+2*d_4= 1+32=33. d_6 = d_1+2*d_5 = 2+2(33)=68. d_7=4 + 2(68)=140. d_8=8+2(140)=288. d_9=16+2(288) = 592. Finally d_(10)=33 + 2(592) = 1217

17. Number of bit strings that contain 00.

I hope we are good at these by now. a_n is the number of bit strings of length n that contain 00. Put a 1 in front of any string of length (n-1) which already contains a 00. This counts for a_(n-1) many strings of length n. We could also put a 0 in front of any bit string of length n-1 which contains 00. This gives another a_(n-1) many strings of length n.

But of course we must also think of strings of length n-1 that start with a 0 which might not contain 00, since putting a 0 in front of string that starts with a 0 gives us a string contain 00 of course. But then we've got to worry about overlap. So we really want those strings of length n-1 that start with a 0 and do not contain 00. Sorry, originally I made a little mistake next:

This is the same as putting a 0 in front of those strings of length n-2 which do not contain 00. How many string are there? Well 2^(n-2) in total and then remove the a_(n-2) that do contain 00.

The mistake: we are trying, at this point, to count the strings of length n-1 that start with a 0 and do not contain 00. Taking a string of length n-1 not containing 00 and putting a 0 in front of it does not always give a string not containing 00 (OF COURSE!).

Correction: This length n-2 substring must start with a 1, so we really have length n-3 strings that do not contain 00. This is the quantity (2^(n-3) - a_(n-3)).

My Final result: a_n = 2 * a_(n-1) + ( 2^(n-3) - a_(n-3) ).

Well the book's answer is a_n= a_(n-1) + a_(n-2) _ 2^(n-2)

Mine (new one) isn't wrong, just different (and higher degree hence not as nice). I got on the wrong (less efficient) course when I decided to put 0 in front of good strings of length n-1. Rather we should have split into cases: 01 in front of good ones of length (n-2) (hence a_(n-2)) plus 00 in front of any of length (n-2). Thus the book's answer.

19. bit strings that do not contain 000

Say that b_n is the number of such strings of length n. b_0=1, b_1=2, b_2=4.

For n>2 we probably have a recurrence. 1 in front of any string of length n-1 which doesn't contain 000 is OK, so this gives b_(n-1) that start with a 1. For those that start with a 0, we can only follow it by a string that starts with a 1 or starts with 01. How many (length n-1 such strings I mean)?
Of course length n-1 starting with a 1 is just b_(n-2). Similarly, length n-1 that start out 01 is just the same as the number of those that are length n-3, i.e. b_(n-3). Recurrence is b_n = b_(n-1) + b_(n-2) + b_(n-3) (linear homogeneous of degree 3).

30. bus driver tossing nickels and dimes into basket.

We did this in class. t_n is the number of ways of tossing in 5n cents. then t_n = t_(n-1) + t_(n-2) (representing either toss in a nickel first, or toss in a dime first).

34. bit strings with even number of 0's.

e_n is the number of length n. build one of length n from shorter ones. Well if you start with a 1 then follow it by a string with an even number of 0's, hence this is e_(n-1) many that start with a 1. If you start with a 0, then it must be followed by a string with an odd number of 0's. Well every string is either even or odd, so there are 2^(n-1) - e_(n-1) many strings with an odd number of 0's. Thus e_n = e_(n-1) + ( 2^(n-1) - e_(n-1) ) = 2^(n-1) (i.e. precisely half the strings!).