Discrete-math 5

Induction #definition

\begin{matrix} P (n), n \in N \\ \begin{matrix} 1. & P (1) \equiv T \\ 2. & \forall n \in N : P (n) \to P (n + 1) \end{matrix} \end{matrix}

\begin{matrix} P (n) \equiv 1 + 2 + \dots + n = \frac{n (n + 1)}{2} \\ Prove: \forall n \in N : P (n) \\ Induction: \\ P (1) \equiv 1 = \frac{1 * 2}{2} \equiv T \\ Let P (n) \equiv T : \\ 1 + 2 + \dots + n = \frac{n (n + 1)}{2} \\ ⟹ 1 + 2 + \dots + (n + 1) = \frac{n (n + 1)}{2} + (n + 1) = \\ = \frac{n (n + 1) + 2 (n + 1)}{2} = \frac{(n + 1) (n + 2)}{2} \\ ⟹ (P (n) \to P (n + 1)) \equiv T \\ ⟹ \forall n \in N : P (n) \end{matrix}

\begin{matrix} In a group of n people, everyone shakes hands with every other member of the group \\ The total number of handshakes is equal to \frac{n (n - 1)}{2} \\ P (n) \equiv f (n) = \frac{n (n - 1)}{2} \\ Induction: \\ P (1) \equiv \frac{1 * 0}{2} = 0 \equiv T \\ Let P (n) \equiv T : \\ f (n + 1) = f (n) + n = \frac{n (n - 1)}{2} + n = \frac{n (n - 1) + 2 n}{2} = \frac{(n + 1) n}{2} \\ ⟹ (P (n) \to P (n + 1)) \equiv T \\ ⟹ \forall n \in N : P (n) \end{matrix}

\begin{matrix} \begin{matrix} 1. & P (m) \equiv T \\ 2. & \forall n \geq m : P (n) \to P (n + 1) \end{matrix} \end{matrix}

\begin{matrix} Prove: \forall n \geq_{2} : P (n) \equiv n! < n^{n} \\ P (2) \equiv 2! < 2^{2} \equiv 2 < 4 \equiv T \\ Let n \geq 2, P (n) \equiv T \\ (n + 1)! = n! (n + 1) < n^{n} (n + 1) < (n + 1)^{n} (n + 1) = (n + 1)^{n + 1} \\ ⟹ (n + 1)! < (n + 1)^{n + 1} \\ ⟹ \forall n \geq 2 : (P (n) \to P (n + 1)) \equiv T \\ ⟹ \forall n \geq 2 : P (n) \end{matrix}

\begin{matrix} \begin{matrix} 1. & P (1) \equiv T \\ 2. & \forall n \in N : (\forall k \leq n : P (k)) \to P (n + 1) \end{matrix} \end{matrix}

\begin{matrix} Prove: \forall n \geq 2 \in N : S (n) \equiv (P (n) \lor (S (a) \land S (b) \land n = a \cdot b)) \\ S (2) \equiv P (2) \equiv T \\ S (n + 1) : \\ \begin{matrix} 1. & P (n + 1) \equiv T ⟹ S (n + 1) \equiv T \\ 2. & P (n + 1) \equiv F ⟹ S (n + 1) \equiv S (a) \land S (b) \land n + 1 = a \cdot b \end{matrix} \\ \exists 2 \leq a, b \leq n : S (a) \land S (b) \land n + 1 = a * b \end{matrix}

\begin{matrix} m \times n = k \\ f (k) = k - 1 \\ P (k) \equiv f (k) = k - 1 \\ P (1) \equiv f (1) = 0 \equiv T \\ m \times n = k + 1 \\ k + 1 = a + b; a \leq k; b \leq k \\ f (a) = a - 1; f (b) = b - 1 \\ f (k + 1) = f (a) + f (b) + 1 = a + b - 2 + 1 = k + 1 - 1 = k \\ ⟹ f (k + 1) = k \end{matrix}