Homework 6-Keeping Track of the Leftovers

1. Keeping Track of the Leftovers (15 points)
Prove the following inequality for all integers n ≥ 2:
nX i
=2
1
(i − 1)i < 1
Hint: What is the sum exactly?
2. Runtime. . . Better Go Catch It! (20 points)
Let c 0 be an integer. The following recursive definition describes the running time of a recursive
algorithm.
T (0) = 0
T (n) ≤ c for all n ≤ 20
T (n) = T ??34n?? + T ?jn5k? + cn for all n 20
Prove by strong induction that T (n) ≤ 20cn for all integers n ≥ 0.
Hint: The only fact about b c that you will need is that when x ≥ 0, bxc is an integer, and 0 ≤ bxc ≤ x.
3. Happily Ever After (15 points)
Let S be the set defined as follows.
Basis Step: 5 2 S; 9 2 S;
Recursive Step: if x; y 2 S, then x + y 2 S.
Show that there is an integer a such that for every integer n ≥ a, it holds that n 2 S.
Hint: Strong induction is the right tool here since the quantifier is not over S.
4. Putting car into Reverse is rac (15 points)
For strings over alphabet Σ, we defined the reversal operation by "R = " and for any w 2 Σ∗ and a 2 Σ
1we have (wa)R = awR. Prove that (x • y)R = yRxR. for all x; y 2 Σ∗.
You may use without proof the fact the (x • (y • z)) = (x • y) • z for all x; y; z 2 Σ∗.
5. Binary Strings (15 points)
For each of the following, write a recursive definition of the sets satisfying the following properties. Briefly
justify that your solution is correct.
(a) [5 Points] Binary strings where every occurrence of a 1 is immediately followed by a 0.
(b) [5 Points] Binary strings with an even number of 1s.
(c) [5 Points] Binary strings with equal number of 0s and 1s.
6. Proving BST Insertion Works! (20 points)
Consider the following definition of a (binary)Tree:
Bases Step: Nil is a Tree.
Recursive Step: If L is a Tree and R is a Tree and x is an integer, then Tree(x; L; R) is a Tree.
The standard BST insertion function can be written as the following:
insert(v; Nil) = Tree(v; Nil; Nil)
insert(v; Tree(x; L; R))) = (Tree Tree( (x; x; L; insert insert (v; L (v; R ); R))) if otherwise. v < x
Next, define a program less which checks if an entire BST is less than a provided integer v:
less(v; Nil) = true
less(v; Tree(x; L; R)) = x < v and less(v; L) and less(v; R)
Prove that for all b 2 Z, x 2 Z and all trees T , if less(b; T ), and b x, then less(b; insert(x; T )).
In English, this means that, given an upper bound on the elements in a BST, if you insert something
that meets that upper bound, it is still an upper bound.
You should use structural induction on T for this question, but there are a few tricky bits that are worth
pointing out up-front:
• You are proving an implication by induction. This means, in your Base Case, you assume the first
part and prove the second one.
• Because of this, there will be two implications going on in your Induction Step. This can be very
tricky. You will assume both your IH and the left side of what you’re trying to prove. You will end
up needing to use both of them at some point in your proof.
• This is the most difficult proof we have given you to date. It would be a mistake to start it on the
last day.
27. Extra Credit: Magical Pebbles (-NoValue- points)
Consider an infinite sequence of positions 1; 2; 3; : : : and suppose we have a pebble at position 1 and
another pebble at position 2. In each step, we choose one of the pebbles and move it according to the
following rule: Say we decide to move the pebble at position i; if the other pebble is not at any of the
positions i + 1; i + 2; : : : ; 2i, then it goes to 2i, otherwise it goes to 2i + 1.
For example, in the first step, if we move the pebble at position 1, it will go to 3 and if we move the
pebble at position 2 it will go to 4. Note that, no matter how we move the pebbles, they will never be
at the same position.
Use induction to prove that, for any given positive integer n, it is possible to move one of the pebbles
to position n. For example, if n = 7 first we move the pebble at position 1 to 3. Then, we move the
pebble at position 2 to 5 Finally, we move the pebble at position 3 to 7.
3