1.
Prove, using induction, that \(\forall n\in\mathbb N\text{,}\) \(3\mid (n^3-n)\text{.}\)
Exercises 7.3 Exercises
2.
Let \(n \in \mathbb{N}\) so that \(n \geq 2\text{.}\) Use mathematical induction to prove that
\begin{equation*}
n! \leq n^n
\end{equation*}
Recall that \(n! = n \cdot(n-1) \cdot(n-2)\cdots 2 \cdot 1\text{.}\)
3.
Let \(n\in\mathbb{N}\text{.}\) Prove that \(\forall n\geq 7\text{,}\) \(n!\gt 3^n\text{.}\)
4.
Let \(n\in\mathbb N\text{.}\) Prove by induction on \(n\text{,}\) that \(\exists x,y,z\in \mathbb Z\) such that \(x\geq 2\text{,}\) \(y\geq 2\text{,}\) and \(z\geq 2\) and satisfy \(x^2+y^2=z^{2n+1}\text{.}\)
5.
Let \(m\in\mathbb{N}\text{,}\) with \(m\) even. Show that \(8\) divides \(3^m-1\text{.}\)
6.
The distributive law says that for any real numbers \(a,b,c\text{,}\) we have
\begin{equation*}
a\cdot(b+c)=a\cdot b+a\cdot c.
\end{equation*}
Use induction to show that for any \(n\geq 2\) and any real numbers \(a,b_1,b_2\dots,b_n\)
\begin{equation*}
a\cdot(b_1+b_2+\dots+b_n)=a\cdot b_1+a\cdot b_2+\dots+a\cdot b_n.
\end{equation*}
7.
Let \(n\in\mathbb{N}\text{.}\) Using induction, prove that \(2^n\geq 2n\text{.}\)
8.
Let \(n\in\mathbb{N}\cup\{0\}\text{.}\) Show that \(5\) divides \(2^{2n+1}+3^{2n+1}\text{.}\)
9.
Let \(n\in\mathbb{N}\text{,}\) \(n\geq 2\text{.}\) Suppose that \(x_1,x_2,\dots,x_n\in\mathbb{Q}\text{.}\) Show by induction that \(x_1+x_2+\dots+x_n\in\mathbb{Q}\text{.}\)
10.
Prove that, \(\forall n\in\mathbb{N}\text{,}\) \(\displaystyle \sum_{k=1}^n k^3=\left( \sum_{k=1}^n k \right)^2\text{.}\)
11.
Prove that \(\sum\limits_{j=1}^n j^3\gt \frac{1}{4}n^4\) for all \(n\in\mathbb N\text{.}\)
12.
Let \(r\) be a real number so that \(r\neq 1\text{.}\) Use induction to show that
\begin{equation*}
\sum_{i=0}^nr^i = \frac{1-r^{n+1}}{1-r}
\end{equation*}
for \(n\in\set{0,1,2,\dots}\text{.}\)
Note: you may have seen a proof of this that does not use induction. Make sure your proof here uses induction.
13.
Let \(k\in \mathbb{N}\text{.}\) Compute the \(k^{\text{th}}\) derivative of the following functions. Use induction to prove that your answer is correct.
- \(f(x) = x^n\) for \(n\in\mathbb{N}\) with \(0\leq k\leq n\text{.}\)
- \(g(x)=x^{-n}\) for \(n\in \mathbb{N}\text{.}\)
- \(h(x) =\frac{1}{\sqrt{9-2x}}\text{.}\)
You may use the chain and power rules in your solutions.
14.
Let \(n\in \mathbb{N}\text{.}\) Prove that
\begin{equation*}
\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}
\end{equation*}
15.
Let \(n\in \mathbb{N}\text{.}\) Show that
\begin{equation*}
\sum_{k=1}^n \frac{1}{2^k} \lt 1
\end{equation*}
16.
Determine why the proposed proof of the following statement is incorrect:
Every non-empty subset \(A\) of the natural numbers has a maximum element. That is, there is some \(a\in A\) such that \(b\leq a\) for all \(b\in A\text{.}\)
Faulty proof.
Let \(A\subseteq\mathbb{N}\) be non-empty. We proceed with induction on \(|A|\text{.}\)
If \(|A|=1\text{,}\) then the single element of \(A\) is its maximum.
Now suppose that \(|A|=n+1\) for some \(n\geq1\text{,}\) and that any subset of \(\mathbb{N}\) of size \(n\) has a maximum element. Choose some \(a\in A\text{,}\) and let \(B=A\setminus\{a\}\text{.}\) Then \(B\subseteq\mathbb{N}\text{,}\) and \(|B|=n\text{.}\) By the inductive hypothesis, \(B\) has a maximum element, say \(b\text{.}\) Therefore \(c\leq b\) for all \(c\in A\setminus\{a\}\text{.}\) If \(a\leq b\) as well, then \(b\) is the maximum element of \(A\text{.}\) If \(b\leq a\text{,}\) then \(c\leq b\leq a\) for all \(c\in A\setminus\{a\}\text{.}\) Therefore \(a\) is the maximum element of \(A\text{.}\)
Taking \(n\to\infty\text{,}\) we see that any non-empty \(A\subset\mathbb{N}\) has a maximum.
17.
Let \(n\in\mathbb{Z}\text{,}\) \(n\geq0\text{.}\)
- Use induction and l’Hôpital’s rule to show that\begin{equation*} \lim_{x\to\infty}x^ne^{-x}=0. \end{equation*}
- Show that\begin{equation*} n! = \int_0^\infty x^ne^{-x}\mathrm{d}x. \end{equation*}
For this question
- recall that \(0!=1\text{,}\) and
- you may use basic facts about limits and integration from your Calculus-1 course.
18.
Let \(a_1, a_2, \ldots\) be real numbers. Prove, using induction, that for all \(n\in\mathbb N\text{,}\)
\begin{equation*}
\left| \sum_{k=1}^n a_k \right|\leq \sum_{k=1}^n|a_k|.
\end{equation*}
You may assume the triangle inequality, \(|x+y|\leq |x|+|y|\) for all real numbers \(x\) and \(y\text{.}\)
19.
All numbers of the form \(1007,10017,100117,1001117,10011117,\dots\) are divisible by \(53\text{.}\)
20.
Let \(F_k\) be the \(k^\mathrm{th}\) Fibonacci number, and let \(q \in \mathbb{N}\text{.}\) Show that \(F_q \mid F_{qn}\) for all \(n \in \mathbb{N}\text{.}\) This generalises Result 7.2.18.
21.
Let \(n,r \in \mathbb{Z}\) so that \(0 \leq r \leq n\text{.}\) We define the binomial coefficient
\begin{equation*}
\binom{n}{r} = \frac{n!}{(n-r)! r!}.
\end{equation*}
- Prove that the binomial coefficients satisfy Pascal’s identity:\begin{equation*} \binom{n+1}{r} = \binom{n}{r} + \binom{n}{r-1} \qquad \text{for } 0 \lt r \leq n \end{equation*}
- and so prove, using induction, the Binomal Theorem:\begin{equation*} (a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k} b^k \end{equation*}for any \(a,b \in \mathbb{R}\) and any \(n \in \mathbb{N}\text{.}\)
22.
Let \(s\in \mathbb{R}\text{,}\) \(s \gt 0\text{.}\) Suppose \(f:\mathbb{R}\to \mathbb{R}\) is a continuous function such that
- for any \(n\in \mathbb{N}\text{,}\) the \(n^\mathrm{th}\) derivative \(f^{(n)}\) exists and is continuous,
- the limit \(\ds \lim_{x\to \infty} e^{-sx}f(x) = 0\text{,}\) and
- for any \(n\in \mathbb{N}\text{,}\) \(\ds \lim_{x\to \infty} e^{-sx}f^{(n)}(x) = 0\)
From \(f\) we can define a new transformed function
\begin{equation*}
\mathcal{L}\{f\}(s) = \int_0^\infty f(x)e^{-sx} \, \mathrm{d}x.
\end{equation*}
Prove that for any \(k \in \mathbb{N}\text{,}\) that
\begin{equation*}
\mathcal{L}\left\{f^{(k)}\right\}(s) = s^k\mathcal{L}\{f\}(x) - \sum_{i=0}^{k-1} s^{k-1-i}f^{(i)}(0)
\end{equation*}
This result tells us that the transform of any derivative is simply related to the transform of the original function. That is, the differential equation in \(f\) turns into an algebraic equation in \(\mathcal{L}(f)\) This sort of result can come in very handy when studying differential equations.
23.
Let \(\alpha\in \mathbb{R}\) such that \(\alpha+\frac{1}{\alpha} \in \mathbb{Z}\text{.}\) Prove that \(\alpha^n+\frac{1}{\alpha^n}\in \mathbb{Z}\) for any \(n\in \mathbb{N}\cup \{0\}\text{.}\)
24.
Show that every natural number, \(n\text{,}\) can be written as
\begin{equation*}
n=3^ma,
\end{equation*}
where \(m\in\mathbb Z\) such that \(m\geq 0\text{,}\) \(a\in\mathbb N\) and \(3\nmid a\text{.}\)
25.
You go on vacation to a foreign country. The local currency only has \(3\) and \(5\) dollar bills, and locals will only give items a price \(p\in \mathbb{N}\) such that \(p\geq 8\text{.}\) Assume that you have access to an unlimited supply of \(3\) and \(5\) dollar bills. Can you buy any souvenir you want? Give a proof or a counterexample.
26.
Let \(a_0,a_1,a_2,\dots\) be a sequence recursively defined as \(a_0=2\text{,}\) \(a_1=1\text{,}\) and
\begin{equation*}
a_n = a_{n-1}+6a_{n-2} \quad \text{for } n\geq 2.
\end{equation*}
Prove by induction that
\begin{equation*}
a_n = (-2)^n+3^n \quad \text{for all } n\geq0.
\end{equation*}
27.
Show that every \(n\in\mathbb N\) can be written in binary. That is, for all \(n \in \mathbb{N}\text{,}\) there exists an \(m\in\mathbb Z\) with \(m\geq 0\) and constants \(c_0,c_1,c_2,\dots, c_m\in\set{0,1} \) such that
\begin{equation*}
a= c_m \cdot 2^m+c_{m-1}\cdot 2^{m-1}+\cdots+c_1\cdot 2+c_0.
\end{equation*}
For example,
\begin{equation*}
537 = 512 + 16 + 8 + 1 = 2^9 + 2^4 + 2^3 + 2^0,
\end{equation*}
so \(m=9\) and \((c_0,c_1,c_2,\dots,c_9) = (1,0,0,1,1,0,0,0,0,1)\text{.}\)
28.
For \(n \in \mathbb{N}\text{,}\) consider the recurrence
\begin{equation*}
T(1)=1 \qquad\text{and for } n \geq 2 \qquad T(n) = 2 T\left( \left\lfloor \frac{n}{2} \right\rfloor \right) + n
\end{equation*}
The first few values of \(T(n)\) are
\begin{equation*}
1, 4, 5, 12, 13, 16, 17, 32, 33, \dots
\end{equation*}
Use strong induction to prove that for \(n \geq 1 \text{,}\) \(T(n) \) satisfies the bound
\begin{equation*}
T(n) \leq n \log_2 n + n.
\end{equation*}
Note that the logarithm has base 2, and that the floor function, \(\lfloor x\rfloor\text{,}\) gives the largest integer smaller or equal to \(x\text{.}\)
Recurrences such as this one appear very frequently in the analysis of “divide and conquer” algorithms. That class of algorithms (roughly speaking) work by repeatedly splitting a larger problem into smaller pieces until they can be solved trivially. The interested reader should search-engine their way to more information.
29.
Use strong induction to prove the following:
Suppose you begin with a pile of \(n\) stones \((n \geq 2)\) and split this pile into \(n\) separate piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile you multiply the number of stones in each of the two smaller piles you form, so that if these piles have \(p\) and \(q\) stones in them, respectively, you compute \(pq\text{.}\) Show that no matter how you split the piles (eventually into \(n\) piles of one stone each), the sum of the products computed at each step equals \(\dfrac{n(n - 1)}{2}\text{.}\)
For example — say with start with \(5\) stones and split them as follows:
\begin{equation*}
(5)\rightarrow
\underbrace{(3)(2)}_{=6}
\rightarrow
\underbrace{(2)(1)}_{=2}
\underbrace{(1)(1)}_{=1}
\rightarrow
\underbrace{(1)(1)}_{=1}(1)(1)(1).
\end{equation*}
Then, we get, \(6+2+1+1=10=\frac{5 \times 4}{2}\quad\checkmark\text{.}\)
