Question 1: In this question, I am generally looking for the proper form of writing an inductive proof. You have to state what you're trying to prove, prove a basis, state a proper inductive hypothesis, and prove the next step. Some of the students call the "inductive hypothesis" an "assumption" inside the proof. For instance they would say something like: f(n+1) = f(n) + 1, and f(n) = n by assumption It would be better to say "by the inductive assumption" or "by the inductive hypothesis" so that there is no ambiguity about what assumption is being used. But in this case, it is a matter of terminology and not a conceptual error so that no credit should have been deducted. Next, a lot of the students did not define a predicate, but just used the sentence throughout. You can save yourself a lot of writing by using a predicate. Some general comments: 1 (a) After you have defined the Predicate P(n) as "the statement (4^n - 1) mod 3 = 0", later on you say something like P(n) = 0 mod 3. If P(n) is a predicate, it does not have a numerical value. This problem runs through all 5 questions, actually, as many people use functions as predicates and vice versa. 1 (b) If your base case is n = 0, then, in order to be able to build up, the first step that you have to work on is P(0) implies P(1). That is why in your induction hypothesis, you need to say "Suppose P(jJ) holds for some n>=0. Now we need to show P holds for n+1". Some of you said "Suppose P holds for some n>=1. Now we need to show P holds for n+1". Saying this would cause a "gap" in your induction. 1 (c) The course notes define the natural numbers as {0, 1, 2, 3, ...}. Some think that the natural numbers are {1, 2, 3, 4, .... } as you use n = 1 as your base case. 1 (d) In your inductive hypothesis, some said "Suppose P holds FOR ALL n>= 0, and we must show P holds for n+1". You should not say "FOR ALL" for your variable in your inductive hypothesis, because that is what you must prove. Question 2: In this question, I am still looking for the proper form of writing an inductive proof. You have to state what you're trying to prove (this criterion is more important in this question, since the theorem that you're asked to prove, f(n) <= 2^(n+1), is different from the claim you're proving), prove a basis, state a proper inductive hypothesis, and prove the next step. 2(a) - (d) are the same as 1(a) - (d). 2(e) Some of the students are proving two things at the same time. For example, some would first say in their induction hypothesis "Suppose f(h) <= 2^(h+1)", and then when they have to use it in their proof, they say "By induction hypothesis, f(n) <= 2^(h+1)-1". You cannot switch between two different sentences. That is also where using a predicate would help to decrease the confusion. 2 (f) Some students do not have a good sense of how an argument should flow from start to finish. A lot of the time, appropriate key words like "implies, if and only if, it is sufficient to prove that" would help make the proof flow better. Question 3: Part (a): This question was done quite poorly. Most did not give a convincing argument. I was looking for the 2 base cases (g(0) = 1 and g(1) = 2) and a sound argument that g(h) = g(h-1) + g(h-2) + 1. Most of you don't give a convincing reason that the two subtrees would have different heights, rather than the same height. Also, many confuse g(i) as a tree. As in 1(a), you have to be very careful about what your symbols represent; that is, does as particular symbol represent a function whose result is an integer, or a predicate which is either true or false. Part (b): This is a standard "complete induction" kind of question. I am looking for the same things as in questions 1 and 2: the proper form of writing an inductive proof. You have to state what you're trying to prove, prove a basis, state a proper inductive hypothesis, and prove the next step. 3 a, c-f the same as question 2. 3 (b) In a complete induction proof, the proper way to write your inductive hypothesis is as follows: (where P is the predicate we try to prove) Let i be an arbitrary integer >= 2. Suppose P(j) is true for all j where 0 <= j < i. We try to prove P(i). Let's examine why we have the above indices. First of all, if we have proved the base cases 0 and 1, the next one that we try to prove is 2. Thus, our inductive statement has to prove P(2), and so i has to be >= 2 since we end up proving P(i). Some wrote "....for all j where 2 <= j < i". However, you should have ".... for all j where 0 <= j < i" because in your proof, you need to assume P(i-1) and P(i-2) to be true. If i=2, then your inductive hypothesis has not included the cases P(0) and P(1), thus the induction won't work. NOTE: Question 3b was erroneously graded out of 5 instead of out of 10. 3 (g) In this question, since the key equation depends on two of the previous cases, you need to show two base cases: g(0) and g(1). Some only gave g(0) as your base case. 3 (h) There has been a misunderstanding on this. I was under the impression that the special cases in the inductive hypothesis must be stated before the inductive statement. The text actually uses this style. Question 4: Part(a): This question was quite well done. The common mistake is that in proving you can trade in 3 8cent stamps for 5 5cent stamps, you didn't make sure that there are at least 3 to start with. Some students took the approach of proving that 28, 29, 30, 31, and 32 cents can be formed by 5 and 8, and then go on to prove that every other number beyond that can be achieved by adding a 5 cent stamp. Part(b): This is also quite well done. The idea is to show that after trying all the possible combinations that may yield 27, we see that it's impossible. Common mistake is that the argument is not strong enough to include all the combinations. Also: 4(i): A lot of you took the approach to say that "The only way to get 27 is take one away from 28, and we need to trade in 5 5cent stamps for 3 8cent stampes or trade in 2 8cent stamps for 3 5cent stampes. Since 28 is made up of 4 5cent stamps and 1 8cent stamp, there isn't enough to trade in and hence you can't get to 27". There are two problems with this: - How do you know that this is the only way to make up 28 with 5 and 8 cent stamps? Maybe there's some other way that would allow for a trade in? - How do you know that decreasing 1 cent is the only way to get 27? Maybe I can make a trade to decrease my value by 2 from my combination of 29? Question 5: The common mistake is that you didn't state the correct loop invariant. Without the proper loop invariant, you will have a lot of trouble in your induction to prove it is correct. Also, many neglected to mention that (y(i) > 0) because we are already executing the (i+1)st iteration. This would affect your argument that y(i+1) >= 0. 5(j) Many said something like "Set k(i) = y(i)/3 - i" or some other formula, showed that k(i) is a decreasing sequence that is non-negative, so it must eventually reach zero, and hence the program halts". However, if we look at the code, the program stops when y = 0, not when some other auxiliary symbol k equals 0. It is sometimes useful to use a new variable, but you have to be careful to show that when this new variable equals zero, the exit condition holds true in the program.