Problem 1

In the following proof:
  1. What is the "size"?
  2. circle and label the the base case
  3. circle and label the the inductive case
  4. Where do we apply the inductive hypothesis?
The formula $\neg(x_1 \vee x_2 \vee \cdots \vee x_{k-1} \vee x_k)$ is equivalent to $\neg x_1 \wedge \neg x_2 \wedge \cdots \wedge \neg x_{k-1} \wedge \neg x_k$.
Induction on $n$ where $n = k - 2$. When $n = 0$, which means $k = 2$, the theorem is just De Morgan's law: $\neg(x_1 \vee x_2) = \neg x_1 \wedge \neg x_2$. So consider $n > 0$, which means $k > 2$. Then since $\vee$ is associative, $$ \neg(x_1 \vee x_2 \vee \cdots \vee x_{k-1} \vee x_k) = \neg((x_1 \vee x_2 \vee \cdots \vee x_{k-1}) \vee x_k) = \neg(x_1 \vee x_2 \vee \cdots \vee x_{k-1}) \wedge \neg x_k $$ then the inductive hypothesis is that for "size" less than $n$ (i.e. fewer than $k$ variables) the theorem holds, so $$ \neg(x_1 \vee x_2 \vee \cdots \vee x_{k-1}) \wedge \neg x_k = (\neg x_1 \wedge \neg x_2 \wedge \cdots \wedge \neg x_{k-1}) \wedge \neg x_k = \neg x_1 \wedge \neg x_2 \wedge \cdots \wedge \neg x_{k-1} \wedge \neg x_k $$ So we deduce that the theorem holds for any size $n$.

Problem 2

Induction is required to really understand computer programs. In the following proof:
  1. What is the "size"?
  2. circle and label the the base case
  3. circle and label the the inductive case
  4. Where do we apply the inductive hypothesis?
//A is an array of n chars
for(int i = 1; i <= n; i++) {	
  printfirst(i,A); // prints first i elements of A
}
Prove that this code prints out $n(n+1)/2$ characters.
We will prove this by induction on $n$, the number of elements in A. When $n=0$ we never enter into the outer loop, since $1 \leq 0$ is false, so we print zero characters and, of course, $n(n+1)/2 = 0$ as well, so the theorem holds. Suppose is $n > 0$. The inductive hypothesis is that the same code with a smaller array, say size $k \lt n$, prints out $k(k+1)/2$ characters. As long as $n > 0$, we can rewrite the code the following way (note that it still prints the same thing): 
//A is an array of n chars
for(int i = 1; i <= (n-1); i++) {	
  printfirst(i,A); // prints first i elements of A
}
printfirst(n,A); // prints all n elements of A
By the inductive hypothesis, the loop prints out $(n-1)((n-1)+1)/2$ characters. The printfirst(n,A) line prints out $n$ characters. So, the total number of characters is these two added together: $$ (n-1)((n-1)+1)/2 + n = (n-1)n/2 + 2n/2 = \frac{(n-1)n + 2n}{2} = \frac{n(n-1+2)}{2} = n(n+1)/2 $$ So we deduce that the theorem holds for any value of $n$.

Problem 3

Suppose A is an array of n characters. Printing the characters "comma-separated" means ... well, it means what you think. For example, if A is , we print it comma separated like this: f,i,e
Consider the following ...

If character array A has $n$ elements, printing it out comma-separated requires $2n$ characters.
Printing an $n$-element array A is the same as printing an $(n-1)$-element array (the first $n-1$ elements of A), followed by a comma and the character A[n-1]. Like this: $$ \underbrace{a_0,a_1,\ldots,a_{n-2}}_{\text{first $n-1$ elements of A}}\ ,a_{n-1} $$ By induction, it takes $2(n-1)$ characters to print the first $n-1$ elements, so the total number of characters required is $$ 2(n-1) + 2 = 2n - 2 + 2 = 2n $$ So no matter how large $n$ is, $2n$ characters are required

According to this "theorem", a three-element array takes six characters to print comma separated, but if you count the previous example, you see actually only five characters are required! So the proof must not be a valid inductive proof. What's wrong with it!

Problem 4

Let $\text{nops}$(·) be the function that returns the number of operators in a propositional formula. So, for example, $\text{nops}(a\wedge b \Rightarrow \neg c) = 3$.

Consider the following purported theorem and proof:

A formula $F$ in which the same variable never appears twice has $\text{nops}(F)+1$ variables.
Let $n = \text{nops}(F)$. Suppose $n = 0$, then $F$ is a variable so F has exactly $n+1 = 1$ variables.✓
Suppose $n > 0$, then consider new formula $G$ defined to be $F \vee x$, where $x$ is a new variable (i.e. not in $F$). Note that $G$ has no repeated variables, and that $\text{nops}(G) = n+1$. By the inductive hypothesis, the number of variables in $G$ is equal to $\text{nops}(G)+1$ which equals $n+2$. Since $G$ has one more variable than $F$, $F$ has $n+1$ variables.✓ So $F$ has $\text{nops}(F)+1$ variables no matter how big $F$ is.

Clearly this "theorem" is wrong, since our example formula $a\wedge b \Rightarrow \neg c$ with three operators has three rather than four variables! But that means the "proof" presented must not be a valid inductive proof. Circle the place in the proof where the error is made, and explain what is wrong with the text you have circled.
Note: do not say that the problem is that the formula could contain $\neg$'s. That's explaining why the "theorem" is wrong, not spotting the error in the proof!

Problem 5

Try to give an inductive proof that the number of variables in a propositional formula $F$ is less than or equal to $\text{nops}(F)+1$.