Exercises
 : shows the complete answer. |  : gives a hint |
 : plays a video solution |  : shows just the final answer |
 : these are important examples that illustrate new concepts, you should be sure to review the solutions to these questions | |
Exercises
Find the derivatives of the following functions.
- Show that $\sum_{i=0}^n a \cdot r^i = \frac{a(1-r^{n+1})}{1-r}$, $n \ge 0$.
- Show that $3 | (2^{2n} - 1)$, $n \ge 1$.
- Show that $2n + 1 < 2^n$, $n \ge 3$.
- Show that $\overline{\cup_{i=1}^n A_i} = \cap_{i=1}^n \overline{A_i}$
- Show that $\sum_{i= 1}^n\left(\frac{1}{i(i + 1)}\right) = \frac{n}{n+1}$, $n \ge 1$.
- Show that $\sum_{i=1}^n(2i - 1) = n^2$, $n \ge 1$.
- Show that $(1 + x)^n \ge 1 + nx$, $n \ge 0$
- Show that a set with $n$ elements has $2^n$ subsets.
- Show that a set with $n$ elements has $\frac{n(n-1)}{2}$ subsets with exactly two elements if $n \ge 2$.
- Show that $\sum_{i=1}^n i(i!) = (n + 1)! - 1$, $n \ge 1$.
- Show that the sum of the first $n$ perfect squares is equal to $\frac{n(n-1)(n+1)}{3}$.
- Show that the sum of the first $n$ perfect cubes is equal to $\left(\frac{n(n+1)}{2}\right)^2$, $n \ge 1$.
- Show that $\prod_{i=0}^n \left(\frac{1}{2i+1}\cdot\frac{1}{2i + 2}\right) = \frac{1}{(2n + 2)!}$, $n \ge 0$.
- Show that $1^2 - 2^2 + 3^2 - . . . + (-1)^{n-1}n^2 = (-1)^{n-1}\frac{n(n+1)}{2}$.
- Show that $3^n \lt n!$, $n \gt 6$.
- Show that $2 | (n^2 + n)$ for all positive integers.
Icons courtesy of icons8.com
Show that $\sum_{i=0}^n a \cdot r^i = \frac{a(1-r^{n+1})}{1-r}$, $n \ge 0$.
Our hypothesis will be $P(n): \sum_{i=1}^n a \cdot r^i = \frac{a(1-r^{n+1})}{1-r}$.
When $n=0$, the left side is $\sum_{i=0}^0 a \cdot r^i = ar^0 = a$ and the right side is $\frac{a(1-r^1)}{1-r} = a$ so the proposition is true for $P(0)$.
Now assume that $P(n)$ is true. We need to show that this makes $P(n+1)$ true. Specifically, we need to show that
$$\sum_{i=1}^{n+1} a \cdot r^i = \frac{a(1-r^{(n+1)+1})}{1-r} = \frac{a(1-r^{n+2})}{1-r}$$Starting with the left side of the induction hypothesis, we have
$$\begin{aligned} \sum_{i=1}^{n+1} a \cdot r^n &=\sum_{i=1}^{n} a \cdot r^n + a\cdot r^{n+1} \\ &=\frac{a(1-r^{n+1})}{1-r} + a\cdot r^{n+1} \\ &=\frac{a(1-r^{n+1})}{1-r} + \frac{a(1-r) \cdot r^{n+1}}{1-r} \\ &=\frac{a(1-r^{n+1})}{1-r} + \frac{a(r^{n+1}-r^{n+2})}{1-r} \\ &=\frac{a(1-r^{n+1}+r^{n+1}-r^{n+2})}{1-r} \\ &=\frac{a(1-r^{n+2})}{1-r} \\ \end{aligned}$$Which is what we needed to show.
Show that $2n + 1 < 2^n$, $n \ge 3$.
- Remember that if $a = b$ and $b < c$ then $a < c$.
- $2 < 2^n$ for values of $n$ that we're considering here.
Show that $2n + 1 < 2^n$, $n \ge 3$.
Our inductive hypothesis will be $P(n): 2n + 1 < 2^n$.
When $n=3$ the left side equals 7 and the right side is 8 so $P(3)$, our basis step, is true.
Now assume that $P(n)$ is true. We need to show that $P(n+1)$ is true or specifically that
$$2(n+1) + 1 < 2^{n+1}$$ $$2n+3 < 2^{n+1}$$Starting with the left side of the inequality, we have
$$\begin{aligned} 2(n+1) + 1 &= 2n + 2 + 1 \\ &= (2n + 1) + 2 \\ &< 2^n + 2\\ &< 2^n + 2^n \\ &= 2 \cdot 2^n \\ &= 2^{n+1} \end{aligned}$$Which is what we needed to show.
Show that $\sum_{i= 1}^n\left(\frac{1}{i(i + 1)}\right) = \frac{n}{n+1}$, $n \ge 1$.
Start by defining $P(n): \sum_{i= 1}^n\left(\frac{1}{i(i + 1)}\right) = \frac{n}{n+1}$.
Then when $n = 1$ the left side becomes $\frac{1}{1(2)} = \frac{1}{2}$ while the right side is $\frac{1}{1+1} = \frac{1}{2}$ so $P(1)$ is true.
Assuming that $P(n)$ is true, we need to show that $P(n+1)$ is true, i.e. that $\sum_{i=1}^{n+1}\left(\frac{1}{i(i + 1)}\right) = \frac{n+1}{(n+1)+1} = \frac{n+1}{n+2}$ $$\begin{aligned} \sum_{i=1}^{n+1}\left(\frac{1}{i(i + 1)}\right) &= \sum_{i=1}^{n}\left(\frac{1}{i(i + 1)}\right) + \frac{1}{(n+1)(n+2)} \\ &=\frac{n}{n+1} + \frac{1}{(n+1)(n+2)} \\ &=\frac{n(n+2)}{(n+1)(n+2)} + \frac{1}{(n+1)(n+2)} \\ &=\frac{n(n+2) + 1}{(n+1)(n+2)} \\ &=\frac{n^2+2n+1}{(n+1)(n+2)} \\ &=\frac{(n+1)^2}{(n+1)(n+2)} \\ &=\frac{n+1}{n+2} \end{aligned}$$
Which is what we needed to show.
Show that $(1 + x)^n \ge 1 + nx$, $n \ge 0$
Remember that if $c > 0$ and $a > b + c$ then we also have $a > b$. In other words, if you take a positive value away from a sum, the result is even smaller than it originally was.
Show that $(1 + x)^n \ge 1 + nx$, $n \ge 0$
Our inductive hypothesis will be $P(n): (1 + x)^n \ge 1 + nx$.
$P(0)$ says that $(1+x)^0 \ge 1 + 0x$ which is true since both sides simplify to 1 for all values of $x$.
Now assume that $(1 + x)^n \ge 1 + nx$ is true. We need to show that $(1 + x)^{n+1} \ge 1 + (n+1)x$.
$$\begin{aligned} (1 + x)^{n+1} &= (1+x)^n(1+x) \\ &\ge (1+nx)(1+x)\\ &=1+nx+x+nx^2 \\ &=1+(n+1)x + nx^2 \end{aligned}$$Now notice that, for all real numbers, $x$, $nx^2 \ge 0$ so if we remove if from $1+(n+1)x+nx^2$ the expression becomes smaller. That means that $$\begin{aligned} (1 + x)^{n+1} &\ge 1+(n+1)x + nx^2 \\ &\ge 1+(n+1)x \end{aligned}$$
Which is what we needed to show.
Show that $\prod_{i=0}^n \left(\frac{1}{2i+1}\cdot\frac{1}{2i + 2}\right) = \frac{1}{(2n + 2)!}$, $n \ge 0$.
Our inductive hypothesis will be $P(n): \prod_{i=0}^n \left(\frac{1}{2i+1}\cdot\frac{1}{2i + 2}\right) = \frac{1}{(2n + 2)!}$.
$P(0)$ says that $\prod_{i=0}^0 \left(\frac{1}{2i+1}\cdot\frac{1}{2i + 2}\right) = \frac{1}{2}$ and $\frac{1}{(2\cdot 0 + 2)!} = \frac{1}{2}$ are equal which is clearly true.
Now assume that $P(n)$ is true. We need to show $P(n+1)$ or $\prod_{i=0}^{n+1} \left(\frac{1}{2i+1}\cdot\frac{1}{2i + 2}\right) = \frac{1}{(2(n+1) + 2)!} = \frac{1}{(2n+4)!}$.
$$\begin{aligned} \prod_{i=0}^{n+1} \left(\frac{1}{2i+1}\cdot\frac{1}{2i + 2}\right) &= \prod_{i=0}^{n} \left(\frac{1}{2i+1}\cdot\frac{1}{2i + 2}\right) \cdot \frac{1}{2(n+1)+1}\cdot\frac{1}{2(n+1) + 2} \\ &=\frac{1}{(2n + 2)!} \cdot \frac{1}{2(n+1)+1}\cdot\frac{1}{2(n+1) + 2} \\ &=\frac{1}{(2n + 2)!} \cdot \frac{1}{2n+3}\cdot\frac{1}{2n + 4} \\ &=\frac{1}{(2n + 4)!} \end{aligned}$$Which is what we needed to prove.
