4.5: Exercises

EXERCISE 4.1. Prove by induction that 3 divides \(7^{n}-4\) for every \(n \in \mathbb{N}^{+}\).

EXERCISE 4.2. Prove by induction that \[(\forall n \in \mathbb{N}) 2^{n}>n .\] EXERCISE 4.3. Prove that any subset of a well-ordered set is wellordered. ExERCISE 4.4. Prove that \((1+x)^{n} \geq 1+n x\) for every \(n \in \mathbb{N}^{+}\)and every \(x \in(-1, \infty)\).

EXERCISE 4.5. Prove by induction that every finite set of real numbers has a largest element.

EXERCISE 4.6. Let \(X\) and \(Y\) be sets with \(n\) elements each. How many bijections from \(X\) to \(Y\) are there? What does this tell you about the number of permutations of \(\ulcorner n\urcorner\) ? Prove your claim.

EXERCISE 4.7. The binomial coefficients \(\left(\begin{array}{l}n \\ k\end{array}\right)\) can be defined from Pascal’s triangle by:

(i) \(\forall n \in \mathbb{N},\left(\begin{array}{l}n \\ 0\end{array}\right)=\left(\begin{array}{l}n \\ n\end{array}\right)=1\).

(ii) \(\forall 2 \leq n \in \mathbb{N}, \forall 1 \leq k \leq n-1,\left(\begin{array}{l}n \\ k\end{array}\right)=\left(\begin{array}{c}n-1 \\ k\end{array}\right)+\left(\begin{array}{c}n-1 \\ k-1\end{array}\right)\).

Prove by induction that \[\left(\begin{array}{l} n \\ k \end{array}\right)=\frac{n !}{(n-k) ! k !} .\] ExERCISE 4.8. Prove the binomial theorem: with \(\left(\begin{array}{l}n \\ k\end{array}\right)\) defined by Exercise 4.7, for any \(n \in \mathbb{N}\), the following identity holds \[(x+y)^{n}=\sum_{k=0}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) x^{n-k} y^{k} .\] ExERCISE 4.9. Prove \(\sum_{k=0}^{n}\left(\begin{array}{l}n \\ k\end{array}\right)=2^{n}\).

EXERCISE 4.10. Prove, for all \(n \in \mathbb{N}^{+}\), \[\left(\begin{array}{c} 2 n \\ n \end{array}\right) \geq \frac{2^{2 n-1}}{\sqrt{n}}\] ExERCISE 4.11. The Principle of Descent says that there is no strictly decreasing infinite sequence of natural numbers. Prove the Principle of Descent.

EXERCISE 4.12. The Fibonacci numbers are defined recursively by \(F_{1}=1, F_{2}=1\), and for \(n \geq 3, F_{n}=F_{n-1}+F_{n-2}\). Prove that the Fibonacci numbers are given by the equation \[F_{n}=\frac{(1+\sqrt{5})^{n}-(1-\sqrt{5})^{n}}{2^{n} \sqrt{5}} .\] This is an example of a formula that is hard to guess, but easy to verify. For an explanation of how the formula arises, see Exercise 5.29.

EXERCISE 4.13. Let \(X\) be a set well-ordered by a relation \(\preceq\). We say that a sequence of elements in \(X,\left\langle x_{n} \mid n \in \mathbb{N}\right\rangle\), is strictly decreasing (with respect to \(\preceq\) ) if for all \(m, n \in \mathbb{N}\) \[[m<n] \Rightarrow\left[x_{n} \preceq x_{m} \wedge x_{n} \neq x_{m}\right] .\] Prove that there is no strictly decreasing sequence of elements in \(X\).

EXERCISE 4.14. Prove that the last digit of \(7^{7} \underbrace{7}\) is 3 for any tower of sevens of height more than 1 .

EXERCISE 4.15. Give another example that illustrates the need for a base case in a valid proof by induction.

EXERCISE 4.16. Assume that there is a polynomial of degree 4 in \(N\) that gives \(\sum_{n=0}^{N} n^{3}\). Find the polynomial and then prove that the formula is correct by induction.

Use Archimedes’s method to prove that

EXERCISE 4.17. Let \(\mathbb{N}[x]\) be the set of polynomials with natural number coefficients. Define a relation \(\preceq\) on \(\mathbb{N}[x]\) by:

Let \(p(x)=\sum_{n=0}^{N} a_{n} x^{n}\), and \(q(x)=\sum_{n=0}^{M} b_{n} x^{n}\). Say that \(p \preceq q\) iff, if \(k\) is the coefficient of highest degree at which \(p\) and \(q\) differ, then \(a_{k} \leq b_{k}\). Is \(\preceq\) a linear ordering? Is it a well-ordering of \(\mathbb{N}[x]\) ?

EXERCISE 4.18. Assume that there is a polynomial \(p\) of degree 5 such that \[\sum_{n=0}^{N} n^{4}=p(N) .\] Find \(p\) and prove that the formula you propose is correct.

EXERCISE 4.19. Determine the set of positive natural numbers \(n\) such that the sum of every \(n\) consecutive natural numbers is divisible by \(n\). EXERCISE 4.20. Let \(f\) be a real function such that, for \(x, y \in \mathbb{R}\), \[f(x+y)=f(x)+f(y) .\] Prove that

a) \(f(0)=0\)

b) \(f(n)=n f(1)\).

EXERCISE 4.21. Prove Corollary 4.9.

EXERCISE 4.22. Consider boxes with dimensions \(a, b\) and \(c\) in which the sum of the dimensions (i.e. \(a+b+c\) ) is fixed. Prove that the box with largest possible volume has dimensions that satisfy \(a=b=c\).

EXERCISE 4.23. Prove by induction that any well-formed propositional statement has a well-defined truth value.

EXERCISE 4.24. Prove by induction on the number of propositional connectives that every compound propositional statement is equivalent to a statement using only \(\neg\) and \(\vee\).

ExERCISE 4.25. Prove by induction on the number of propositional connectives that every compound propositional statement is equivalent to a statement using only \(\neg\) and \(\wedge\).

EXERCISE 4.26. Let \(Q_{i}\) be a quantifier, for \(1 \leq i \leq n\). For each \(Q_{i}\), let \(Q_{i}^{*}\) be the complementary quantifier. That is, if \(Q_{i}=\forall\), then \(Q_{i}^{*}=\exists\); if \(Q_{i}=\exists\), then let \(Q_{i}^{*}=\forall\). Prove by induction on the number of quantifiers that, \(\neg\left(Q_{1} x_{1}\right)(\ldots)\left(Q_{n} x_{n}\right) P\left(x_{1}, \ldots, x_{n}\right) \equiv\left(Q_{1}^{*} x_{1}\right)(\ldots)\left(Q_{n}^{*} x_{n}\right) \neg P\left(x_{1}, \ldots, x_{n}\right) .\)

EXERCISE 4.27. Define the \(n^{\text {th }}\) Fermat number to be \[F_{n}:=2^{2^{n}}+1, \quad n \in \mathbb{N} .\] (i) Show that the Fermat numbers satisfy \[\prod_{k=0}^{n} F_{k}=F_{n+1}-2 .\] (ii) Conclude that any two distinct Fermat numbers are coprime. EXERCISE 4.28. Let \(\left\langle a_{n}: n \in \mathbb{N}\right\rangle\) be a sequence of positive numbers. Suppose that \(a_{0} \leq 1\), and that for all \(N \in \mathbb{N}\), \[a_{N+1} \leq \sum_{n=0}^{N} a_{n} .\] Prove \[(\forall N \in \mathbb{N}) a_{n} \leq 2^{N}\] EXERCISE 4.29. Let \(\left\langle a_{n}: n \in \mathbb{N}\right\rangle\) be a sequence of positive numbers satisfying (4.21), and \(a_{0} \leq C\). What is the correct analogue of (4.22)? Prove your assertion.

EXERCISE 4.30. Let \(\mathcal{F}=\left\{X_{\alpha} \mid \alpha \in A\right\}\) be an indexed family of pairwise disjoint sets. Suppose that each \(X_{\alpha}\) is well-ordered by \(\preceq_{\alpha}\) and that \(A\) is well-ordered by \(\preceq\). Define a relation \(R\) on the union of all the sets in \(\mathcal{F}\) by: for all \(a, b \in \bigcup_{\alpha \in A} X_{\alpha}, a R b\) iff (a) \(a \in X_{\alpha_{1}}, b \in X_{\alpha_{2}}\) and \(\alpha_{1} \preceq \alpha_{2}\),

or

(b) \((\exists \alpha \in A) a, b \in X_{\alpha}\) and \(a \preceq_{\alpha} b\).

Prove that \(R\) is a well ordering of \(\bigcup_{\alpha \in A} X_{\alpha}\).

EXERCISE 4.31. Let \(X\) be a finite set and \(f: X \rightarrow X\). Prove that \(f\) is an injection iff \(f\) is a surjection.