Important! These are all exam-level problems. Do not attempt these problems without a solid foundation in the subject and use them for exam practice.
1. Bob the Bug is on a window, trying to escape Sally the Spider. Sally has built her web from the ground to 2 inches up the window. Every second, Bob jumps 1 inch vertically up the window, then loses grip and falls to half his vertical height. Prove that no matter how high Bob starts up the window, he will always fall into Sally’s net in a finite number of seconds.
Base case: If he starts at a height less than 3, then he is guarenteed to go up 1 inch, to a maximum of 4, then fall back half of his height, which is 2. Hence, in one time step, he will end up in Sally's net.
Inductive Hypothesis: Assume he falls into the net in finite time if he starts for all height less than n inches above the ground.
Inductive step: We must now prove that in height n+1 inches above the ground, Bob will fall into Sally's net in finite time. If n+1 is less than 3 inches, then the base case applies directly. Otherwise, when he takes one step up, for n+1 > 3, the distance which he falls is euqal to (n+1) - (n+2) / 2, which is greater than 1 for n+1 > 3. Hence, Bob falls atleast an inch if not more from time time step, and applying the inductive hypothesis, we know from there, Bob will fall into Sally's net in finite time. 2. Prove that Σ from i=0 to n of i!i is equal to (n+1)! - 1 for n >= 1 and n in the natural numbers.
Base case: For n = 1, we get 0 + 1*1! = (1+1)! - 2, which is true as 1 = 1
Induction Hypothesis: Assume that this is true for n = k.
Inductive Step: Let's prove this for k+1. Σ from i = 0 to k+1 of (i)!*i = Σ from i = 1 to k of i*(i+1) + (k+1)(k+1)!
= (k+1)! - 1 + (k+1)(k+1)! by the inductive hypothesis,
=(k+1)!(k+2) - 1
=(k+2)! - 1
=(k+1+1)! - 1
Hence, we have proven it for k+1, and it is true for all n. 3. Let {0,1}* be the set of all binary strings, and let y * z be the concatenation of the strings y an z. Prove that every string x ∈ {0,1}* can be written in the form x = y * z, where the number of 0's in y is the same as the number of 1's in z. We can have empty strings.
There are two answers, one using strong induction and one using weak. They follow the same idea, so I will prove it using simple induction. Let n denote the length of the string.
Base case: n = 0, the empty string, which is the empty string * the empty string, which satisfies our contraints.
Inductive step: Assume for n = k, this holds true.
Inductive hypothesis: We must prove this for n = k+1. So, let's first worry about the first n elements of our substring which, from our inductive hypothesis can be split into some y and some z, which we will call y' and z'. Now, we must worry about this last element. There are only two cases:
Xn+1 = 0, then just add this element to z' as the amount of 0s in y' and the amount of 1s in z' will remain equal.
Xn+1 = 1, then we must worry about the first element of z'. Let's call this element the j+1th element. If it is a 0, then we will include this j+1th element in y' instead, as now it will have gained a 0 and z' will have gained a 1 (the n+1th element), so they will be equal. If the j+1th element, however, is a 1, then we can still include it in y' instead, as though z' gained a 1 in the n+1th element, it lost one in the j+1th element, so the amount of 1s didn't really change.
Hence, by induction, this proves for all n.