Proposition 1.5 $2^n \gt n$ for all integer $n \geq 0$
Proof. Base Step. The initial statement $S(0): 2^0 \gt 0$ is true, for $2^0 = 1 > 0$
Inductive Step. If $S(n)$ is true, then $S(n+1)$ is true.
If $2^n \gt n$ is true, then
$2^{n+1} = 2 \cdot 2^n \gt 2n = n + n \geq n+1 (n \geq 1)$
Hence, $2^{n+1} \gt 2n \geq n + 1$, then $2^{n+1} \gt n + 1$
$2^n \gt n$ for all $n \geq 0$
Proposition 1.6 $1 + 2 + \dots n = \frac{1}{2} n (n + 1)$ for every integer $n \geq 1$
Proof. The proof is by induction on $n \geq 1$
Base Step. If $n = 1$, then $1 = \frac{1}{2} \times 1 \times (1 + 1) = 1$
$Inductive Step.$ $S(n+1)$: $1 + 2 + \dots + n + (n+1) = \frac{1}{2}n(n+1)+(n+1)$
$= \frac{1}{2}(n(n+1) + 2(n+1))$
$= \frac{1}{2}(n+1)(n+2)$
$= \frac{1}{2}(n+1)[(n+1)+1]$
By induction, the formula holds for all $n \geq 1$
Proposition 1.8 $2^n \gt n^2$ is true for all integer $n \geq 5$
Proof. Base Step. $n = 5$. $2^5 = 32 \gt 5^2 = 25$
Inductive Step. $n \geq 5$. $2^{n+1} = 2 \cdot 2^n \gt 2 \cdot n^2$
$= n^2 + n^2 = n^2 + n \cdot n \gt n^2 + 3n = n^2 + 2n + n$
$\gt n^2 + 2n + 1 = (n+1)^2$
$Q.E.D.$
Exercises
1.1 Find a formula for $1 + 3 + 5 + \dots + (2n-1)$. and use mathematical induction to prove that your formula is correct.
$1 + 3 + 5 + \dots + (2n-1) = n^2$
Proof. Base Step. $n = 1$ $1 = 1^2 = 1$
Induction Step. $n \geq 1$
$1 + 3 + 5 + \dots + (2n-1) + [2(n+1)-1]$
$= n^2 + [2(n+1)-1]$
$= n^2 + 2n + 2 - 1$
$= n^2 + 2n + 1$
$= (n+1)^2$
$Q.E.D.$
1.2 Find a formula for $1 + \sum_{j=1}^{n} j!j$. and use induction to prove that your formula is correct.
$1 + \sum_{j=1}^{n} j!j = (n+1)!$
Proof. Base Step. $n=1$ $1+1!1 = 2 = (1+1)!$
Inductive Step. $n \geq 1$
$1 + \sum_{j=1}^{n+1} j!j$
$= 1 + \sum_{j=1}^{n} j!j + (n+1)!(n+1)$
$= (n+1)! + (n+1)!(n+1)$
$= (n+2)!$
$Q.E.D.$
1.3 (i) For any $n \geq 0$ and any $r \neq 1$. prove that $1 + r + r^2 + r^3 + \dots + r^n = \frac{1-r^{n+1}}{1-r}$
Proof. Base Step. $n = 0$ $1 = \frac{1 - r^{0+1}}{1-r} = 1 (r \neq 1)$
Inductive Step. $n \geq 1$
$1 + r + r^2 + r^3 + \dots + r^n + r^{n+1}$
$= \frac{1-r^{n+1}}{1-r} + r^{n+1}$
$= \frac{1 - r^{n+1} + r^{n+1} - r \cdot r^{n+1}}{1-r}$
$= \frac{1-r^{n+2}}{1-r}$
$Q.E.D.$
1.3(ii) Proof that $1 + 2 + 2^2 + \dots + 2^n = 2^{n+1} - 1$
Proof. Base Step. $n = 0$ $1 = 2^{0-1} - 1 = 1$
$Inductive Step.$ $n \geq 0$
$1 + 2 + 2^2 + \dots + 2^n + 2^{n+1}$
$= 2^{n+1} - 1 + 2^{n+1}$
$= 2^{n+2} - 1$
$Q.E.D.$
1.4 Show for all $n \geq 1$. that $10^n$ leave remainder 1 after dividing by 9
Proof. Base Step. $n=1$ $10^1 \equiv 1 (\mod{9})$
Inductive Step. $n \geq 1$ $10^{n+1} = 10^n \cdot 10 = 10^n \times 9 + 10^n$
Then $10^{n+1} \equiv 10^n \times 9 + 10^n \equiv (0+1) \equiv 1 (\mod{9})$
$Q.E.D.$
1.5 Prove that if $0 \leq a \leq b$, then $a^n \leq b^n$ for all $n \geq 0$
Proof. Base Step. $n = 0$ $a^0 = b^0$
$Inductive Step.$ $n \geq 0$ $a^{n+1} = a^n \cdot a \leq a^n \cdot b \leq b^b \cdot b = b^{n+1}$
$Q.E.D.$
1.6 Prove that $1^2 + 2^2 + \dots + n^2 = \frac{1}{6}n(n+1)(2n+1) = \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n$
Proof. Base Step. $n=1$ $1^2 = \frac{1}{3} + \frac{1}{2} + \frac{1}{6} = 1$
Inductive Step. $n \geq 1$
$1^2 + 2^2 + \dots + n^2 + (n+1)^2$
$= \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n + (n+1)^2$
$= \frac{1}{6}(2n^3 + 9n^2 + 13n + 6)$
$= \frac{1}{6}(2n^3 + 6n^2 + 6n + 2) + \frac{1}{6}(3n^2 + 6n + 3) + \frac{1}{6}(n+1)$
$= \frac{1}{3}(n+1)^3 + \frac{1}{2}(n+1)^2 + \frac{1}{6}(n+1)$
$Q.E.D.$
1.7 Prove that $1^3 + 2^3 + \dots + n^3 = \frac{1}{4}n^4 + \frac{1}{2}n^3 + \frac{1}{4}n^2$
1.8 Prove that $1^4 + 2^4 + \dots + n^4 = \frac{1}{5}n^5 + \frac{1}{2}n^4 + \frac{1}{3}n^3 - \frac{1}{30}n$