159.255 - Assignment 3
Due at or before 5pm Monday 8 May
No extensions will be given under any circumstances

Note: Answer as many questions as you can. Let n be your score and x be the maximum score of any student in this assignment. Then the contribution of this assignment to your final grade = $\left\{ \begin{array}{ll} 15n/x & {\rm if\ } x \not = 0\\ 0 & {\rm otherwise}\\ \end{array}\right.$ Points will be given for all serious attempts to solve the problems, even if correct answers are not obtained.

1.

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

2.

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

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$

4.

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

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)]$

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).

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$.

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.

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$.

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).

The following are strictly for fun and don't contribute to your final

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?

12.

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