Induction, continued

Induction

In Section 10.1, the book proves the following propositions by applying the axiom of induction.

  1. If \(n\in\mathbb{N}\), then \(1+3+5+\cdots+(2n-1)=n^2\)
  2. If \(n\) is a non-negative integer, then \(5|(n^5-n)\).
  3. If \(n\in\mathbb{Z}\), and \(n\ge 0\), then \(\sum_{i=0}^{n} i\cdot i! = (n+1)!-1.\)
  4. If \(n\in\mathbb{N}\), then \(2^n\le 2^{n+1}-2^{n-1}-1\).
  5. If \(n\in\mathbb{N}\), then \((1+x)^n\ge 1+nx\) for all \(x\in\mathbb{R}\) with \(x>-1\).

YOU SHOULD CAREFULLY STUDY ALL OF THESE PROOFS

Two notes: Problem 3 has \(n\ge 0\) and Problem 5 has an additional variable.

Triangular numbers (Exercise 1)

Proposition: Prove that \(1+2+3+\cdots+n = \frac{n^2+n}{2}\).

Geometric series

Proposition: For any \(n\ge 0\), \[ 1+x+\cdots+x^n = \frac{x^{n+1}-1}{x-1} \]

A result on sets (Problem 17)

Proposition: Suppose that \(A_1,A_2,\cdots, A_n\) are sets contained in a universal set \(U\) and that \(n\ge 2\). Then \[ \overline{\bigcap_{i=1}^{n} A_{i}} = \bigcup_{i=1}^{n} \overline{A_{i}} \]