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_(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!).