<aside> 🔖 Re-Reading

Before Reading Week, we briefly discussed the topics of Big-$O$, Big-$Ω$, and Big-Θ notation, the first of

which had previously been mentioned in our discussion of nested quantifiers. The text covers these topics

in section 3.2, and you may find it is useful to read that account when working on part B.

</aside>

Cauchy-Induction

$P(2)$ is true

\$\forall k\ge 3 P(k)\rarr P(k-1)$

$\forall k\ge 1 P(2^k)\rarr P(2^{k+1})$

Note. This is not the correct setup to apply induction. But we still can show that $\forall n\ge 2\ P(n)$

Let $R(k)$ be $P(2^k)$

the rules say $R(1)$ is true

and $\forall k\ge 1\ R(k)\rarr R(k+1)$

$\therefore \forall n\ge1\ R(n)$ is true.

We can deal with the arrow in the second rule running the wrong way by consider $Q(k)=\neg P(k)$, then we have $\neg Q(k) \rarr \neg Q(k-1)\ \forall k\ge 3$

so by contrapositive $Q(k-1)\rarr Q(k)\ \forall k\ge 3$

and thus $Q(k) \rarr Q(k+1)\ \forall k\ge 2$ (There were tow substitutions here Let $\mathbf{l} =k-1$ then at then end let $k=1$)

Assume, for contradiction, that $\exist n\ge 2\ \Big(Q(n)\Big)$

then by induction $\forall l\ge n\ Q(l)$

Now, in particular $2^n\ge n$ so $Q(2^n)$ is true,

but then P(2^n) is false

but $P(2^n)$ is R(n) so R(n) is false.