Exercises

Exercises 7.4 Exercises

1.

Prove by induction that \(\displaystyle \sum_{i=0}^n (4i+1) = 2n^2 + 3n + 1\) for all integers \(n \ge 0\text{.}\)

Hint: \(4+1 = 2+3\text{.}\)

2.

Prove by induction for all integers \(n \ge 1\text{,}\) that \(\displaystyle \sum_{i=1}^n i^2 = \dfrac{n(n+1)(2n+1)}{6}\text{.}\)

Hint.

Hint: The “factoring trick” will help here.

3.

Prove by induction for all integers \(n \ge 1\text{,}\) that \(\displaystyle \sum_{i=1}^n i^2 = \dfrac{n(n+1)(2n+1)}{6}\text{.}\)

Hint.

Hint: The “factoring trick” will help here.

4.

Prove by induction that as long as \(r \neq 1\) and for all integers \(n \ge 0\text{,}\) that \(\displaystyle \sum_{i=0}^n r^i = \dfrac{r^{n+1}-1}{r-1}\text{.}\)

Hint.

Hint: Just treat \(r\) like you would any number (that isn't equal to \(1\)— do you see why?). This is known as the formula for a finite geometric series.

5.

Using induction, prove \(\displaystyle \sum_{i=1}^n \frac{1}{i(i+1)} = \frac{n}{n+1}\) for all \(n \ge 1\text{.}\)

6.

Prove by induction that for all integers \(n \ge 6\text{,}\) \(n^2+5n+1 \le 2n^2\text{.}\)

7.

Prove by induction that \(n^2+7n+3 \le 3n^2\) for all integers \(n \ge 4\text{.}\)

8.

Prove using induction that \(n^2+3n+10 \le 4n^2\) for all \(n \ge 3\text{.}\)

9.

Prove by induction that \(2n+1 \le 2^n\) for all \(n \ge 4\text{.}\)

Hint.

Hint: \(2^{k+1} = 2^k + 2^k\text{.}\)

10.

Prove by induction that \(n^2 \le 2^n\) for all \(n \ge 4\text{.}\)

Hint.

Hint: Use the result from the preceding exercise.

11.

Prove by induction that \(n^3+3n+1 \le 2n^3\) for all integers \(n \ge 2\text{.}\)

Hint.

Hint: \((k+1)^3 = k^3+3k^2+3k+1\text{.}\)

12.

Prove by induction that a set with \(n\) elements has \(2^n\) subsets for all \(n \ge 0\text{.}\)

Solution.

Solution: Consider a set with no elements, i.e. \(\varnothing\text{.}\) The sole subset of \(\varnothing\) is \(\{\varnothing\}\text{,}\) so the set with \(n=0\) elements has \(2^0 = 1\) subset.

Inductively, assume that any set with \(k\) elements has \(2^k\) subsets if \(k\) is an integer where \(k \ge 0\text{.}\)

Now, consider the set \(X\) with \(k+1\) elements. Without loss of generality, list them:

\begin{equation*} X = \{x_1, x_2, \ldots, x_k, x'\} \end{equation*}

Observe that \(X\) can be decomposed into two sets:

\begin{equation*} X = S \cup \{x'\} \end{equation*}

where

\begin{equation*} S = \{x_1, x_2, \ldots, x_k\} \end{equation*}

Any subset of \(X\) can be grouped into two categories, one that contains \(x'\) and one that does not. Any subset that does not contain \(x'\) is a subset of \(S\text{,}\) and we know by the inductive hypothesis that \(S\) has \(2^k\) subsets. Any subset that does contain \(x'\) can be decomposed into \(E \cup \{x'\}\) where \(E \subseteq S\text{;}\) there are also \(2^k\) of these.

So, there are \(2^k + 2^k = 2^{k+1}\) subsets of \(X\text{.}\) By induction, a set with \(n\) elements has \(2^n\) subsets.