\documentclass[12pt, std]{article} \usepackage{amssymb} \begin{document} \begin{center} \textbf{Induction.} \end{center} In this section assume the notational convention that $n \in \mathbb{N}$ where $\mathbb{N}$ denotes the positive integers. For some of these theorems we need to divide, so we need multiplicative inverses; and you'll find those in the AxiomsOfTheReals.pdf file. So you may use the axioms of the reals in this section plus (obviously) the induction Axiom. You may assume all the usual algebraic assumptions about the real numbers that you learned in High School. Because of the similarity of the axioms of the reals to those of the integers, you should be able to generalize the theorems about the integers to the real numbers and verify all those rules you used in High School Mathematics courses. (And, for example, the generalizations of Theorem 3.1 a-l.) There are two axioms that I feel require special study, the induction axiom and the completeness axiom. We will first concentrate on the induction axiom; you will likely need it to prove the following theorems. \ Theorem 4.1. If $n \in \mathbb{N}$ then, $$\sum_{i=1}^n i = \frac{n(n+1)}{2}.$$ [The numbers $T_n = \sum_{i=1}^n i$ are called triangular numbers. (Why?)] \ Theorem 4.2. If $n \in \mathbb{N}$ then, $$\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}.$$ \ Theorem 4.3. If $n \in \mathbb{N}$ then, $$\sum_{i=1}^n i^3 = \Big{[}\frac{n(n+1)}{2}\Big{]}^2.$$ \ Exercise 4.1. First prove the following lemma [this is called a ``telescoping series'']: Lemma: $$\sum_{i=1}^n (a_i - a_{i-1}) = a_n - a_0.$$ Then observe that $\sum_{i=1}^n (i+1)^3 - i^3$ is a telescoping series and then use the lemma to find the sum. Then expand each term of the sum by distributing the summation symbol to obtain an equation and solve for $\sum i^2$ in terms of $\sum i$. Then use theorem 4.1 to obtain the formula of theorem 4.2. \ Exercise 4.2. Repeat exercise 4.1 only replace 2 with 3, then with 4 and 5 and obtain the summation formula for $\sum i^3$ and $\sum i^4$. Verify the second formula by induction for practice with induction arguments. \ Definition: Let $n\in \mathbb{N} \cup \{0\}$, if $n=0$ then we define $0! = 1$, if $n \ne 0$ we define $(n+1)! = (n+1) \cdot n!$. \ Exercise 4.3. Verify for each positive integer $n$: $$\sum_{i=1}^n i\cdot i! = (n+1)! -1.$$ \ Exercise 4.4. \qquad a. Verify for each positive integer $n$: $$1 + \frac n2 \le \sum_{i=1}^{2^n} \frac 1i \le 1 + n.$$ [Note that the first inequality can be used to show that the harmonic series diverges.] \qquad b. Verify for each positive integer $n$, $(2n)!<2^{2n}(n!)^2$. \ Theorem 4.4. If n is a positive integer and x and y are real numbers then $x-y$ is a factor of $x^n-y^n$. \ Definition. The Fibonacci numbers $\{F_n\}_{i=1}^{\infty}$ are defined as follows: \qquad $F_1 = 1$. \qquad $F_2 = 1$. \qquad For $n\in \mathbf{Z}, n>2$, $F_{n+1}=F_n + F_{n-1}$. \ Exercise 4.5. Calculate: \qquad a. $\sum_{i=1}^n F_i$, \qquad b. $\sum_{i=1}^n F_{2i-1}$. \ Theorem 4.5. For each positive integer $n$: \qquad a. $\sum_{i=1}^n F_i^2 = F_nF_{n+1}$, \qquad b. $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$, \qquad c. If $n>2$, then $F_{n+1}F_{n} - F_{n-1}F_{n-2} = F_{2n-1}$, \qquad d. $\sum_{i=1}^{2n-1} F_{i}F_{i+1} = [F_{2n}]^2$. \ Exercise 4.6. Let $n$ be a positive integer. Show that: \qquad a. $F_n \le 2^{n-1}$, \qquad b. $F_n \le {\frac 74}^{n-1}$, \qquad c. If $\beta = \frac {1+\sqrt{5}}{2}$, then $F_n \le \beta^{n-1}$. [Note: $\beta^2 = \beta + 1$.] \ Theorem 4.6. Let $\alpha$ and $\beta$ be the roots of $x^2=x+1$ with $\alpha < \beta $, then: $$F_n= \frac {\beta^n - \alpha^n}{\sqrt{5}}.$$ \ Exercise 4.7. Let $ M = \pmatrix{1 &1\cr 1 &0}.$ Then $ M^n= \pmatrix{F_{n+1} &F_n\cr F_n & F_{n-1}}.$ \ Exercise 4.8. Verify: $$ \sum_{i=1}^{n} 2i-1 = n^2.$$ \ \end{document}