Chapter 5

A "postage stamp problem" is a problem that (typically) asks us to determine what total postage values can be produced using two sorts of stamps. Suppose that you have \(3 \mathrm{c}\) stamps and \(7 \mathrm{c}\) stamps, show (using strong induction) that any postage value \(12 \mathrm{c}\) or higher can be achieved. That is, $$ \forall n \in \mathbb{N}, n \geq 12 \quad \Longrightarrow \quad \exists x, y \in \mathbb{N}, n=3 x+7 y. $$

Give inductive proofs of the following $$ \forall x \in \mathbb{N}, 3 \mid x^{3}-x $$

Show that any integer postage of \(12 \&\) or more can be made using only \(4 \mathrm{c}\) and \(5 \mathrm{c}\) stamps.

Give inductive proofs of the following $$ \forall x \in \mathbb{N}, 3 \mid x^{3}+5 x $$

What is wrong with the following inductive proof of "all horses are the same color."? Theorem Let \(H\) be a set of \(n\) horses, all horses in \(H\) are the same color. Proof: We proceed by induction on \(n\). Basis: Suppose \(H\) is a set containing 1 horse. Clearly this horse is the same color as itself. Given a set of \(k+1\) horses \(H\) we can construct two sets of \(k\) horses. Suppose \(H=\left\\{h_{1}, h_{2}, h_{3}, \ldots h_{k+1}\right\\}\). Define \(H_{a}=\left\\{h_{1}, h_{2}, h_{3}, \ldots h_{k}\right\\}\) (i.e. \(H_{a}\) contains just the first \(k\) horses ) and \(H_{b}=\left\\{h_{2}, h_{3}, h_{4}, \ldots h_{k+1}\right\\}\) (i.e. \(H_{b}\) contains the last \(k\) horses). By the inductive hypothesis both these sets contain horses that are "all the same color." Also, all the horses from \(h_{2}\) to \(h_{k}\) are in both sets so both \(H_{a}\) and \(H_{b}\) con- tain only horses of this (same) color. Finally, we conclude that all the horses in \(H\) are the same color.

Give inductive proofs of the following $$ \forall x \in \mathbb{N}, 11 \mid x^{11}+10 x $$

Give inductive proofs of the following $$ \forall n \in \mathbb{N}, 3 \mid 4^{n}-1 $$

Suppose that the rules of the game for PMI were changed so that one did the following: \- Basis. Prove that \(P(0)\) is true. \- Inductive step. Prove that for all \(k, P_{k}\) implies \(P_{k+2}\) Explain why this would not constitute a valid proof that \(P_{n}\) holds for all natural numbers \(n\). How could we change the basis in this outline to obtain a valid proof?

Give inductive proofs of the following $$ \forall n \in \mathbb{N}, 6 \mid\left(3 n^{2}+3 n-12\right) $$

Prove the following formula for a product. $$ \prod_{i=2}^{n}\left(1-\frac{1}{i}\right)=\frac{1}{n} $$

Give inductive proofs of the following $$ \forall n \in \mathbb{N}, 5 \mid\left(n^{5}-5 n^{3}+14 n\right) $$

Prove \(\sum_{j=0}^{n}(4 j+1)=2 n^{2}+3 n+1\) for all integers \(n \geq 0\).

Give inductive proofs of the following $$ \forall n \in \mathbb{N}, 4 \mid\left(13^{n}+4 n-1\right) $$

Prove \(\sum_{i=1}^{n} \frac{1}{(2 i-1)(2 i+1)}=\frac{n}{2 n+1}\) for all natural numbers \(n\).

The Fibonacci numbers are a sequence of integers defined by the rule that a number in the sequence is the sum of the two that precede it. $$ F_{n+2}=F_{n}+F_{n+1} $$ The first two Fibonacci numbers (actually the zeroth and the first) are both 1 . Thus, the first several Fibonacci numbers are $$ F_{0}=1, F_{1}=1, F_{2}=2, F_{3}=3, F_{4}=5, F_{5}=8, F_{6}=13, F_{7}=21, \text { et cetera } $$ Use mathematical induction to prove the following formula involving Fibonacci numbers. $$ \sum_{i=0}^{n}\left(F_{i}\right)^{2}=F_{n} \cdot F_{n+1} $$

Give inductive proofs of the following $$ \forall n \in \mathbb{N}, 6 \mid 2 n^{3}-2 n-12 $$

Give inductive proofs of the following $$ \forall n \geq 3 \in \mathbb{N}, 3 n^{2}+3 n+1<2 n^{3} $$

Give inductive proofs of the following $$ \forall n>3 \in \mathbb{N}, n^{3}<3^{n} $$

Give inductive proofs of the following $$ \forall n \geq 3 \in \mathbb{N}, n^{3}+3>n^{2}+3 n+1 $$