Description
Preliminaries:
Review logic symbols here: http://en.wikipedia.org/wiki/List_of_logic_symbols
Read about truth tables here:
http://sites.millersville.edu/bikenaga/math-proof/truth-tables/truth-tables.html
1. Negate the following statements. For each one, construct a truth table to prove that your negation is
correct. Note that “or” in logic is always non-exclusive!
(a) (P ∧ Q)
(b) (P ∨ Q)
2. Negate the following statements. No truth table is required. You do not have to provide your steps.
It is enough to just give an answer.
(a) For every integer n, 2n + 1 is odd.
(b) For some integer n, 2
n + 1 is prime.
(c) Let A be an n × n real matrix and λ ∈ R . Statement: ∃ v ∈ R
n, v 6= 0, such that Av = λv.
(d) Let f : R → R be a function. Statement: ∀ η > 0, ∃ δ > 0 such that |x| ≤ δ =⇒ |f(x)| ≤ η|x|
3. Prove that √
7 is irrational. In your proof, you may use as true the following statement: “Let m be
an integer. If 7 divides m2
, then 7 also divides m.”
4. Let A be a square matrix. Prove: If det(A) = 0, then A is not invertible.
Remark:
(a) As part of your solution, look up the definition of an inverse of a matrix and write it down
carefully.
(b) You may use as known: det(AB) = det(A) det(B) for square matrices of the same size.
5. Prove that, for all integers n ≥ 1,
Pn
k=1
1
k(k+1) =
n
n+1 .
6. These use strong induction:
(a) Prove that, for all integers n ≥ 12, there exist non-negative integers k1 and k2 such that n =
k14 + k25. Is the same statement true for n ≥ 8?
(b) Prove that, for all even integers n ≥ 6, there exist non-negative integers k1 and k2 such that
n = k13 + k25.
7. More Lagrange Multipliers: Let M be an n×n real symmetric matrix. Use the method of Lagrange
multipliers to do the following
(a) For x ∈ R
n, solve max x
>Mx, subject to the constraint, x
>x = 1. Find both the maximum value
and an x that solves the problem.
(b) For x ∈ R
n, solve min x
>Mx, subject to the constraint, x
>x = 1. Find both the minimum value
and an x that solves the problem.
Hints
Hints: Prob. 2 For (c) and (d), you may find it easier to replace the symbols ∀ and ∃ by appropriate words
in English BEFORE you negate the statement. Once you have negated the statement expressed in English,
reinsert the symbolic expression as appropriate. With practice, you can skip this intermediate step.
In (d), there is an implied quantifier. Here is an equivalent statement that I will call (d’) Let f : R → R
be a function. Statement: (d’) ∀ η > 0, ∃ δ > 0 such that ∀x ∈ R satisfying |x| ≤ δ it is true that |f(x)| ≤ η|x|
Another way to think about the statement: Let Aδ := {x ∈ R | |x| ≤ δ}.
(d”) ∀ η > 0, ∃ δ > 0 such that x ∈ Aδ implies |f(x)| ≤ η|x|
Hints: Prob. 3 Definition: An integer m divides an integer n if there exists an integer k such that n = mk.
Hints: Prob. 5 Write down carefully P(n), followed by the base case, the induction step, and what is to
be shown. Then the problem becomes easy.
Hints: Prob. 6 (a) is worked in the handout, except for the part about n ≥ 8. For (b), you should really
try to do it without any further help.
Hints: Prob. 7
• No additional hints given in Office Hours! This can be a hard problem. If you get it, great! If not, no
big deal, study the solution and remember the answer. We will use the result later in the term. This
could have been part of HW 1, but I wanted to keep the initial HW set as short as possible.
• x is a column vector and thus x
>Mx is a scalar.
• When you form your Lagrange function, write it as x
>Mx + λ(1 − x
>x).
• Eigenvalues of real symmetric matrices are real; the eigenvectors are real too. You can easily find
proofs of this on the web.
• Because the eigenvalues are real and finite in number, there exists a largest eigenvalue, denoted λmax,
and a smallest eigenvalue, denoted λmin.
• For a symmetric matrix M,
∂
∂x (x
>Mx) = 2Mx, where we are writing the gradient as a column vector,
with i-th entry ∂
∂xi
(x
>Mx). Though we are not doing so here, it is often more convenient to write it
as a row vector, in which case ∂
∂x (x
>Mx) = 2x
>M (recall that M is symmetric).
3
