4.01b Complex proofs: conjecture and demanding proofs

9. (i) A sequence of numbers is defined by $$\begin{gathered} u _ { 1 } = 6 , \quad u _ { 2 } = 27 \\ u _ { n + 2 } = 6 u _ { n + 1 } - 9 u _ { n } \quad n \geqslant 1 \end{gathered}$$ Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\) $$u _ { n } = 3 ^ { n } ( n + 1 )$$ (ii) Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\) $$f ( n ) = 3 ^ { 3 n - 2 } + 2 ^ { 3 n + 1 } \text { is divisible by } 19$$ \includegraphics[max width=\textwidth, alt={}, center]{536d7ec7-91b0-4fda-a485-2ac4a72c7d59-29_56_20_109_1950}

1

1. Use a truth table to prove \(\sim ( \sim \mathrm { T } \Rightarrow \sim \mathrm { S } ) \Leftrightarrow ( \sim \mathrm { T } \wedge \mathrm { S } )\).
2. Prove that \(( \mathrm { A } \Rightarrow \mathrm { B } ) \Leftrightarrow ( \sim \mathrm { A } \vee \mathrm { B } )\) and hence use Boolean algebra to prove that $$\sim ( \sim \mathrm { T } \Rightarrow \sim \mathrm {~S} ) \Leftrightarrow ( \sim \mathrm { T } \wedge \mathrm {~S} ) .$$
3. A teacher wrote on a report "It is not the case that if Joanna doesn't try then she won't succeed." He meant to say that if Joanna were to try then she would have a chance of success. By letting T be "Joanna will try" and S be "Joanna will succeed", find the real meaning of what the teacher wrote.

1

1. A joke has it that army recruits used to be instructed: "If it moves, salute it. If it doesn't move, paint it." Assume that this instruction has been carried out completely in the local universe, so that everything that doesn't move has been painted.
   1. A recruit encounters something which is not painted. What should he do, and why?
   2. A recruit encounters something which is painted. Do we know what he or she should do? Justify your answer.
2. Use a truth table to prove \(( ( ( m \Rightarrow s ) \wedge ( \sim m \Rightarrow p ) ) \wedge \sim p ) \Rightarrow s\).
3. You are given the following two rules. $$\begin{aligned} & 1 \quad ( a \Rightarrow b ) \Leftrightarrow ( \sim b \Rightarrow \sim a ) \\ & 2 \quad ( x \wedge ( x \Rightarrow y ) ) \Rightarrow y \end{aligned}$$ Use Boolean algebra to prove that \(( ( ( m \Rightarrow s ) \wedge ( \sim m \Rightarrow p ) ) \wedge \sim p ) \Rightarrow s\).

1

1. The Plain English Society presents an annual "Foot in Mouth" award for "a truly baffling comment". In 2004 it was presented to Boris Johnson MP for a comment on the \(12 ^ { \text {th } }\) December 2003 edition of "Have I Got News For You":
   "I could not fail to disagree with you less."
   1. Explain why this can be rewritten as:
      "I could succeed in agreeing with you more."
   2. Rewrite the comment more simply in your own words without changing its meaning.
2. Two switches are to be wired between a mains electricity supply and a light so that when the state of either switch is changed the state of the light changes (i.e. from off to on, or from on to off). Draw a switching circuit to achieve this. The switches are both 2-way switches, thus: \includegraphics[max width=\textwidth, alt={}, center]{88acde67-e22b-478a-9145-48abe931beff-2_127_220_895_1054}
3. Construct a truth table to show the following. $$[ ( a \wedge b ) \vee ( ( \sim a ) \wedge ( \sim b ) ) ] \Leftrightarrow [ ( ( \sim a ) \vee b ) \wedge ( a \vee ( \sim b ) ) ]$$

2

1. Emelia: 'I won't go out for a walk if it's not dry or not warm.'
   Gemma: 'It's warm. Let's go!'
   Will what Gemma has said convince Emelia, and if not, why not?
2. If it is daytime and the car headlights are on, then it is raining. If the dashboard lights are dimmed then the car headlights are on.
   It is daytime.
   It is not raining.
   1. What can you deduce?
   2. Prove your deduction.
3. In this part of the question the switch X is represented by \includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-3_104_138_824_1226} The switch can be wired into a circuit so that current flows when
   the switch is up \includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-3_103_177_1005_593}
   but does not flow when it is down \includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-3_111_167_1000_1334} Or the switch can be wired so that current flows when
   the switch is down \includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-3_109_172_1228_639}
   but does not flow when it is up \includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-3_109_174_1228_1327}
   1. Explain how the following circuit models \(( \mathrm { A } \wedge \mathrm { B } ) \Rightarrow \mathrm { C }\). \includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-3_365_682_1484_694} In the following circuit B1 and B2 represent 'ganged' switches. This means that the two switches are either both up or both down. \includegraphics[max width=\textwidth, alt={}, center]{d254fbd2-7443-4b6d-87ba-f0d71fce5e17-3_364_1278_2042_397}
   2. Given that A is down, C is up and current is flowing, what can you deduce?

In this question you must show detailed reasoning.

1. Explain why all cubic equations with real coefficients have at least one real root. [2]
2. Points representing the three roots of the equation \(z^3 + 9z^2 + 27z + 35 = 0\) are plotted on an Argand diagram. Find the exact area of the triangle which has these three points as its vertices. [7]

You are given that \(q \in \mathbb{Z}\) with \(q \geqslant 1\) and that $$S = \frac{1}{(q+1)} + \frac{1}{(q+1)(q+2)} + \frac{1}{(q+1)(q+2)(q+3)} + \cdots$$

1. By considering a suitable geometric series show that \(S < \frac{1}{q}\). [3]
2. Deduce that \(S \notin \mathbb{Z}\). [2]

You are also given that \(\mathrm{e} = \sum_{r=0}^{\infty} \frac{1}{r!}\).

1. Assume that \(\mathrm{e} = \frac{p}{q}\), where \(p\) and \(q\) are positive integers. By writing the infinite series for \(\mathrm{e}\) in a form using \(q\) and \(S\) and using the result from part (b), prove by contradiction that \(\mathrm{e}\) is irrational. [3]

The set \(X\) consists of all \(2 \times 2\) matrices of the form \(\begin{pmatrix} x & -y \\ y & x \end{pmatrix}\), where \(x\) and \(y\) are real numbers which are not both zero.

1. 1. The matrices \(\begin{pmatrix} a & -b \\ b & a \end{pmatrix}\) and \(\begin{pmatrix} c & -d \\ d & c \end{pmatrix}\) are both elements of \(X\). Show that \(\begin{pmatrix} a & -b \\ b & a \end{pmatrix}\begin{pmatrix} c & -d \\ d & c \end{pmatrix} = \begin{pmatrix} p & -q \\ q & p \end{pmatrix}\) for some real numbers \(p\) and \(q\) to be found in terms of \(a\), \(b\), \(c\) and \(d\). [2]
   2. Prove by contradiction that \(p\) and \(q\) are not both zero. [5]
2. Prove that \(X\), under matrix multiplication, forms a group \(G\). [You may use the result that matrix multiplication is associative.] [4]
3. Determine a subgroup of \(G\) of order 17. [2]

**In this question you must show detailed reasoning.** It is given that \(f(z) = z^3 - 13z^2 + 65z - 125\). The points representing the three roots of the equation \(f(z) = 0\) are plotted on an Argand diagram. Show that these points lie on the circle \(|z| = k\), where \(k\) is a real number to be determined. [9]