# Exercises - Induction in Other Contexts

$$\require{AMSsymbols}$$

1. Use mathematical induction to prove the given inequalities are true for the indicated values of $n$.

1. $\displaystyle{3^n \gt 2n}$;   $n=1,2,3,\ldots$

2. $\displaystyle{n^2 \gt 2n+1}$;   $n=3,4,5, \ldots$

3. $\displaystyle{2^n \gt n^2}$;   $n=5,6,7,\ldots$

4. $\displaystyle{2^n \lt n!}$;   $n=4,5,6,\ldots$

5. $\displaystyle{1 + \frac{1}{4} + \frac{1}{9} + \cdots + \frac{1}{n^2} \le 2 - \frac{1}{n}}$;   $n=1,2,3,\ldots$

6. $\displaystyle{(1+x)^n \ge 1 + nx}$;   $n=1,2,3,\ldots$

2. Use mathematical induction to prove that if $n \in {\Bbb Z^+}$, then the following statements are true.

1. $17^n - 12^n$ is divisible by $5$   $n=1,2,3,\ldots$

2. There exist distinct integers $x$, $y$, and $z$ for which $x^2 + y^2 + z^2 = 14^n$ (Hint: you might want to consider even n and odd n separately.)

3. $n^3+n$ is even

3. Prove that if $n$ is an integer greater than or equal to 2, and the below radical contains exactly $n$ ones, it must be irrational.

$$\sqrt{1 + \sqrt{1 + \sqrt{1 + \sqrt{1 + \cdots}}}}$$

4. Use mathematical induction to prove that for $n>23$, there exists non-negative integers $x$ and $y$ such that $n=7x+5y$.

5. What is wrong with the following proof that all horses in any group of $n$ horses are the same color?

Basis Step.

Certainly, all horses from a group of $n=1$ horses are the same color -- there's only one horse after all.

Inductive Step.

Assume that all horses in a group of $k$ horses are the same color for some positive integer $k$. Now consider a group of $k+1$ horses. Suppose we name these horses: $h_1,h_2,h_3,\ldots,h_k, h_{k+1}$. Notice that horses $h_1,h_2,\ldots,h_k$ is a group of $k$ horses, and hence, must all be of the same color. Also, horses $h_2,h_3,\ldots,h_{k+1}$ is also a group of $k$ horses, and hence, must all be of the same color. Since these two groups of horses have common members (i.e., horses $h_2,h_3,\ldots,h_k$), all $k+1$ horses must be of the same color. Then by the principle of mathematical induction, for any positive integer $n$, all horses in any group of $n$ horses are the same color.

6. A jigsaw puzzle is solved by putting its pieces together in the correct way. Show that exactly $n-1$ moves are required to solve a jigsaw puzzle with $n$ pieces, where a move consists of putting together two blocks of pieces, with a block consisting of one or more assembled pieces. (Hint: Use the second principle of mathematical induction.)

7. Suppose a function $f(n)$ is defined in the following way: $f(1)=1$, $f(2)=5$, and for $n \ge 2$, $f(n+1)=f(n)+2f(n-1)$. Conjecture a formula for $f(n)$, assuming $n$ is always a natural number (i.e., positive integer), and prove your conjecture. (Hint: Use the second principle of mathematical induction.)

8. The tower of Hanoi was a popular puzzle of the late nineteenth century. The puzzle includes three pegs and some number of rings of different sizes placed in order of size, with the largest on the bottom, on one of the pegs. The goal of the puzzle is to move all the rings, one at a time without ever placing a larger ring on top of a smaller ring, from the first peg to the second, using the third peg as an auxiliary peg.

1. Experiment to discover a formula that gives the minimum number of moves required to transfer $n$ rings, and then use induction to prove your conjecture.

2. An ancient legend tells of the monks in a tower with 64 gold rings and 3 diamond pegs. They started moving the rings, one move per second, when the world was created. When they finish transferring the rings to the second peg, the world ends. How long will the world last?

9. Suppose a sequence $x_1,x_2,\ldots$ is defined by $x_1 = 5$, $x_2 = 13$, and $x_{n+1}=5x_n - 6x_{n-1}$ for $n \ge 2$. Prove that $$x_n = 2^n + 3^n$$

10. Show that for any integer $n \ge 0$ we have $$\int_0^{\infty} x^n e^{-x} dx = n!$$

11. Prove that for every integer $n \ge 1$, $$\frac{d^n}{dx^n} \left[ xe^{2x} \right] = 2^{n-1}(2x+n)e^{2x}$$

12. Let $a_1, a_2, \ldots$ be a sequence of real numbers satisfying $a_{i+j} \le a_i + a_j$ for all positive integers $i$ and $j$. Use the principle of strong induction to prove:

$$a_n \le a_1 + \frac{a_2}{2} + \frac{a_3}{3} + \cdots + \frac{a_n}{n}$$

◆ ◆ ◆