159.255 - Assignment 2: Solutions

1.

(a) Prove that the maximum contribution of this assignment to your final grade is 15 points.

Answer. Assume n is my score and x is the maximum score of any student in the class. Since I am a member of this class, $n \not > x$. Equivalently $n \le x$ or $n/x \le 1$. So $15n/x \le 15$. Thus the maximum contribution of the assignment to my final grade is 15.

(b) Prove that letting a friend copy your correct answer to a question may reduce the contribution of your own assignment to your final grade.

Answer. Proof by example. Let my friend currently have the maximum score, x, in class. Suppose I let him copy one of my correct answers and thereby increase his score to y > x, while my own score, n, remains unchanged. Then since y > x, 1/y < 1/x. Consequently, my new score, 15n/y < 15n/x, my old score.

2.

Prove that $\log_2 3$ is irrational (i.e. $\not =$ the quotient of two integers).

Answer. Proof by contradiction. Suppose $\log_2 3$ is rational. Then $\log_2 3 = a/b$ for some integers a and b. Then by definition of the logarithm, 3 = 2^a/b giving 3^b = 2^a. But 2 and 3 are prime and so $2^a \not = 3^b$ for integer a and b. This is a contradiction and so $\log_2 3$ must be irrational. (Alternately, you could say the equality never holds because the RHS is even and the LHS is odd $\forall a,b$)

3.

Using truth tables, prove that the following implication is a tautology: $[(p \vee q) \wedge (p \rightarrow r) \wedge (q \rightarrow r)] \rightarrow r$

Answer. See the following table:

			u	v	w	x
p	q	r	$p \vee q$	$p \rightarrow r$	$q \rightarrow r$	$u \wedge v \wedge w$	$x \rightarrow r$
F	F	F	F	T	T	F	T
F	F	T	F	T	T	F	T
F	T	F	T	T	F	F	T
F	T	T	T	T	T	T	T
T	F	F	T	F	T	F	T
T	F	T	T	T	T	T	T
T	T	F	T	F	F	F	T
T	T	T	T	T	T	T	T

4.

Show that the proposition $[\neg p \wedge (p \vee q)] \rightarrow q$ is a tautology without using truth tables.

Answer. Direct proof.

$$\begin{eqnarray*}[\neg p \wedge (p \vee q)]\rightarrow q &\Leftrightarrow& (\ne... ...ightarrow& p \vee {\rm\bf T}\\ &\Leftrightarrow& {\rm\bf T}\\ \end{eqnarray*}$$

5.

Translate the following proposition into English where ${\rm\bf Z}$ is understood to stand for the set of all integers: $\forall n,m \in {\rm\bf Z} [\exists p (p = (m+n)/2)]$

Answer. For all pairs of integers, there exists a number equal to their mean. (Or equivalent translation).

6.

Translate the following proposition into one in the standard symbolic notation used in the prescribed text: If n raised to the power c is an integer for all positive integer values of n, then c is also an integer. Conjecture its truth value. (Note: Proof not necessary, but is welcome).

Answer. $\forall c \in {\rm\bf R}\ [\forall n \in {\rm\bf Z}\ (n > 0) \wedge n^c \in {\rm\bf Z}] \rightarrow c \in {\rm\bf Z}$ where ${\rm\bf R} \supseteq {\rm\bf Z}$ is understood to stand for the set of all real numbers. (Or equivalent translation. Note the positioning of the brackets.)

7.

Derive a formula for the sum: $\sum_{i=0}^n 2i^2 + 5i + 3$ in each of the following two ways and show their equivalence.

a)

By assuming the sum to be a polynomial that is O(n³), i.e. an³ + bn² + cn + d.

b)

By decomposing the sum into 3 separate sums and using the following information: $\sum_{i=0}^n i^2 = n(n+1)(2n+1)/6$ and $\sum_{i=0}^n i = n(n+1)/2$.

Answer. (a) Let $\sum_{i=0}^n 2i^2 + 5i + 3 = an^3 + bn^2 + cn + d$. Setting n = 0, 1, 2, 3 gives the following simultaneous linear equations:

d = 3 (1)

a+b+c+d = 13 (2)

8a + 4b + 2c + d = 34 (3)

27a + 9b + 3c + d = 70 (4)

Solving for a,b,c and d gives $\sum_{i=0}^n 2i^2 + 5i + 3 = \frac{2}{3}n^3 + \frac{7}{2}n^2 + \frac{35}{6}n + 3$.

Answer. (b)

$$\begin{eqnarray*}\sum_{i=0}^n 2i^2 + 5i + 3 &=& 2\sum_{i=0}^n i^2 + 5 \sum_{i=0}^n i + \sum_{i=0}^n 3\\ &=& 2n(n+1)(2n+1)/6 + 5n(n+1)/2 + 3(n+1) \end{eqnarray*}$$

Simplifying, we get $\sum_{i=0}^n 2i^2 + 5i + 3 = \frac{2}{3}n^3 + \frac{7}{2}n^2 + \frac{35}{6}n + 3$.

8.

Write a program to compute the above sum for all n, $0 \le n < 10$ first using the formula you have derived above and then actual calculation by iterative addition. Attach the code for your program and its output. Both the program and its output should fit neatly on a single page.

Answer. Program:

main()
{
  double sum1 = 0, sum2 = 0;
  unsigned n, i;
  
  for (n = 0; n < 10; n++) {
    sum1 = sum2 = 0;
    sum1 = 2.0/3.0 *n*n*n + 7.0/2.0*n*n + 35.0/6.0*n + 3;
    for (i = 0; i <= n; i++)
      sum2 += 2*i*i + 5*i + 3;
    printf("n = %2d: By addition=%g and by formula=%g\n",
            n, sum2, sum1);
  }
} /* Or equivalent program */

Output:

n =  0: By addition = 3 and by formula = 3
n =  1: By addition = 13 and by formula = 13
n =  2: By addition = 34 and by formula = 34
n =  3: By addition = 70 and by formula = 70
n =  4: By addition = 125 and by formula = 125
n =  5: By addition = 203 and by formula = 203
n =  6: By addition = 308 and by formula = 308
n =  7: By addition = 444 and by formula = 444
n =  8: By addition = 615 and by formula = 615
n =  9: By addition = 825 and by formula = 825

9.

Explain how you can determine the largest value of n for which n! has fewer than 1000 decimal digits. Give this value. Hint: Use the fact that $\log ab = \log a + \log b$.

Answer. Find the least n such that $S = \log_{10} n! = \sum_{i=1}^n \log_{10} i \ge 999$. Since $\log_{10} n! \ge 999, n!$ must be $\ge 10^{999}$, i.e. not less than 1 followed by 999 zeros. n-1 is thus the required number whose factorial has fewer than 1000 digits.

10.

A certain class has n students where n > 2. Using mathematical induction, prove that it is possible to form n(n-1)(n-2)/6 different groups of exactly 3 students from this class. (i.e. Prove that a set with n elements has n(n-1)(n-2)/6 subsets containing exactly three elements whenever n > 2).

Answer. Assume the proposition is true for n. Then there are n(n-1)(n-2)/6 subsets of size 3 from a set of size n> 2. Consider a set of size n+1. The number of extra 3-element sets that can be formed is equal to the number of number of distinct 2-element sets that can be formed from the original n-element set since each of these can be combined with the new n+1st element. Thus the total number of 3-element subsets from the n+1-element set is ``n choose 2'' which is n(n-1)/2 plus n(n-1)(n-2)/6 (by the inductive hypothesis). This equals n(n-1)/2 + n(n-1)(n-2)/6 = (n+1)n(n-1)/6 = (n+1)(n+1-1)(n+1-2)/6 proving the hypothesis.

11.

If you answer this question correctly you will get 1 point for it. Otherwise you will get 0 points for it. How many points will you get for this question?

Answer. 1 (If your aim is to get a point), 0 (if your aim is to make a point), excuse the pun.

12.

Is the result of this test decidable (for all possible inputs)?

Answer. Clearly no. Consider the answer ``0'' to the previous question.