🔬 Problem set alpha

🔬 Problem set alpha#

\(\alpha\).1#

Consider the statement All students taking ECON6012 class are admitted at ANU

  • Write this statement in the form \(P \implies Q\)

  • Is this a true statement?

  • Write down the converse of the statement. Is it true?

  • Write down the contrapositive for the statement. Is it true?

Review the definitions of the terms converse and contrapositive.

  1. \(P\) is students taking ECON6012 class, \(Q\) is admitted at ANU. We have \(P \implies Q\) because all students satisfying \(P\) (\(P\) is true) are also satisfying \(Q\) (\(Q\) is true).

  2. It is a true statement: indeed in order to attend a class one has to be admitted at ANU.

  3. Converse takes the form \(Q \implies P\): All students admitted at ANU are taking ECON6012. Clearly false.

  4. Contrapositive is \(\neg Q \implies \neg P\): Those not admitted at ANU are not taking ECON6012. This one is again true.

\(\alpha\).2#

This is an exercise on necessary and sufficient conditions. Start with some definitions from geormetry:

  • a quadrilateral is a planar figure made up of four line segments connected to form a closed shape. Consider only simple quadrilaterals without self-intersections.

  • a quadrilateral with a pair of parallel sides is called a trapezoid

  • a quadrilateral with two pais of parallel sides is called a parallelogram

  • a parallelogram with right angles is called a rectangle

  • a rectangle with all sides of the same length is called a square

  • a parallelogram with all sides of the same length is called a rhombus

illustration

For each of the statements below determine if they are True or False. For those which are False, provide a counterexample.

  1. Sufficient condition for a quadrilateral to be a square is for it to be a rhombus.

  2. Necessary condition for a quadrilateral to be a square is for it to be a rectangle.

  3. Sufficient condition for a quadrilateral to be a rectangle is for it to be a parallelogram.

  4. Necessary condition for a quadrilateral to be a rectangle is for it to be a parallelogram.

  5. Necessary condition for a quadrilateral to be a parallelogram is for it to be a trapezoid.

  6. Sufficient condition for a quadrilateral to be a parallelogram is for it to be a square.

  7. Necessary condition for a quadrilateral to be a trapezoid is for it to be a rhombus.

  8. Necessary condition for a quadrilateral to be a rectangle is for it to be a trapezoid.

  9. Necessary and sufficient conditions for a quadrilateral to be a square are for it to simultaneously be a rectangle and a rhombus.

Use the following notation:

  • \(T\) trapezoid

  • \(P\) parallelogram

  • \(R\) rectangle

  • \(S\) square

  • \(B\) rhombus

Inspecting the conditions in the definitions we have the following implications:

\[ T \impliedby P \impliedby R \impliedby S \implies B \implies P \]

It is important to stare at these implications and convince your that you agree with each \(\implies\) and each \(\impliedby\).

Therefore correct answers are

  1. False. We don’t have \(B \implies S\); counterexample is a rhombus without right angles

  2. True. We do have \(R \impliedby S\)

  3. False. We don’t have \(P \implies R\); counterexample is a parallelogram without right angles

  4. True. We do have \(P \impliedby R\)

  5. True. We do nave \(T \impliedby P\)

  6. True. We do have \(S \implies P\) (through intermediate \(R\))

  7. False. We do have \(B \impliedby T\); counterexample is a trapezoid with bases of different lengths

  8. True. We do have \(T \impliedby R\) (through intermediate \(P\))

  9. True. We do have \((R \text{ and } B) \impliedby S\) and \((R \text{ and } B) \implies S\)

\(\alpha\).3#

Using direct proof, show that the difference between a cube of a natural number greater than one, \(n=2,3,\dots\), and the number itself is divisible by 6.

Factor the expression \(n^3-n\) and use the property of the consecutive natural numbers.

Denote the given number \(p\). Simple algebra gives \(p = n^3-n = n(n^2-1) = (n-1)n(n+1)\). For \(n = 2,3,\dots\), we conclude that \(p\) is a product of three consecutive natural numbers.

It is easy to show that among \(k\) consecutive natural numbers at least one is divisible by \(k\) (this can be proven by contradiction using the pigeonhole principle and the number of non-zero remainders).

From the above, it follows that at least one number among \(n-1\), \(n\), and \(n+1\) is divisible by 3, and by considering any subsequence of two elements, at least one number is divisible by 2. Therefore, their product \(p\) is divisible by both 2 and 3, that is by 6. \(\blacksquare\)

\(\alpha\).4#

Prove by contradiction that \(\sqrt{3}\) is an irrational number (so that is it can not be represented by a ratio of two whole numbers).

Assume the opposite, namely that \(\sqrt{3} = \frac{p}{q}\) where without loss of generality whole numbers \(p\) and \(q\) do not have common factors.

  1. Assume that \(\sqrt{3} = \frac{p}{q}\) where \(p\) ad \(q\) are whole numbers.

  2. Without loss of generality we can choose \(p\) and \(q\) such that they do not have common factors, otherwise these factors can be cancelled out.

  3. Then \(\frac{p^2}{q^2} = 3\), and so \(3q^2 = p^2 \iff p^2\) is a multiple of 3.

  4. All components in prime decomposition of \(p^2\) enter in pairs because it is a square, therefore there must be an even number of 3’s in the factorization of \(p^2\) \(\implies\) \(p\) is a multiple of 3 itself.

  5. Therefore we can find a whole number \(r\) such that \(p = 3r\), and substitute to get \(3q^2 = 9r^2 \implies q^2 = 3r^2\).

  6. Now the same arguments applied to \(q\) let us conclude that \(q\) is also a multiple of 3.

  7. This contradicts our choice of \(p\) and \(q\) not having common factors!

  8. Therefore our assumption that \(\sqrt{3} = \frac{p}{q}\) is false, and thus \(\sqrt{3}\) is indeed an irrational number. \(\blacksquare\)

\(\alpha\).5#

Using mathematical induction prove that \(n < 2^n\) holds for all natural numbers \(n=1,2,\dots\).

Verify the statement holds for \(n=1\), and assuming \(n<2^n\) prove that \(n+1 < 2^{n+1}\).

First, we note that for \(n=1\) the statement holds: \(1 < 2^1\). This forms the bases for mathematical induction.

Second, assuming that the statement is true for \(n\), i.e. \(n < 2^n\), we need to prove that it holds for \(n+1\), i.e. \(n+1 < 2^{n+1}\).

  1. multiplying both sides of \(n < 2^n\) by 2 we have \(2n < 2^{n+1}\)

  2. but \(n+1 < 2n\) for all \(n > 1\) because the difference \(2n - (n+1) = n-1\) is always positive for \(n > 1\)

  3. we have \(n+1 < 2n < 2^{n+1}\), therefore taking the leftmost and rightmost inequality we have \(n+1 < 2^{n+1}\)

The first and the second parts together form the base of the induction and the induction step. The statement is therefore true for all \(n=1,2,\dots\). \(\blacksquare\)

Note

The symbol \(\blacksquare\) marks the end of the proof, and is equivalent to the QED symbol (”quod erat demonstrandum”, or “that which was to be demonstrated”).

Contents