Exercises: Induction proofs of identities and divisibility
Let $P(n)$ be the statement $1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$. a) Verify that $P(1)$ is true. b) Write down $P(k)$ and $P(k+1)$. c) Assuming $P(k)$ is true,…
Let $P(n)$ be the statement $1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$.
- a) Verify that $P(1)$ is true.
- b) Write down $P(k)$ and $P(k+1)$.
- c) Assuming $P(k)$ is true, show that $P(k+1)$ is true.
Let $P(n)$ be the statement $1 + 3 + 5 + \dots + (2n-1) = n^2$. a) Show that $P(1)$ and $P(2)$ are true. b) Assuming $P(k)$ is true for some $k \in \mathbb{N}$, prove…
Let $P(n)$ be the statement $1 + 3 + 5 + \dots + (2n-1) = n^2$.
- a) Show that $P(1)$ and $P(2)$ are true.
- b) Assuming $P(k)$ is true for some $k \in \mathbb{N}$, prove that $P(k+1)$ is true.
Prove by induction that $4^n - 1$ is divisible by 3 for all $n \in \mathbb{N}$. Begin by checking the case $n = 1$, then show that $4^{k+1} - 1 = 4(4^k - 1) + 3$.
Prove by induction that $4^n - 1$ is divisible by 3 for all $n \in \mathbb{N}$. Begin by checking the case $n = 1$, then show that $4^{k+1} - 1 = 4(4^k - 1) + 3$.
Prove by induction that, for all $n \in \mathbb{N}$, $$1 + r + r^2 + \dots + r^{n-1} = \frac{r^n - 1}{r - 1}, \quad r \neq 1.$$
Prove by induction that, for all $n \in \mathbb{N}$,
$$1 + r + r^2 + \dots + r^{n-1} = \frac{r^n - 1}{r - 1}, \quad r \neq 1.$$Prove by induction that, for all $n \in \mathbb{N}$, $$1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}.$$
Prove by induction that, for all $n \in \mathbb{N}$,
$$1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}.$$Prove by induction that $7^n - 1$ is divisible by 6 for all $n \in \mathbb{N}$.
Prove by induction that $7^n - 1$ is divisible by 6 for all $n \in \mathbb{N}$.
Prove by induction that, for all $n \in \mathbb{N}$, $$\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \dots + \frac{1}{n(n+1)} = \frac{n}{n+1}.$$
Prove by induction that, for all $n \in \mathbb{N}$,
$$\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \dots + \frac{1}{n(n+1)} = \frac{n}{n+1}.$$Prove by induction that $5^n + 2\cdot 11^n$ is divisible by 3 for all $n \in \mathbb{N}$.
Prove by induction that $5^n + 2\cdot 11^n$ is divisible by 3 for all $n \in \mathbb{N}$.
Let $z = \cos\theta + i\sin\theta$. Prove by induction that $z^n = \cos n\theta + i\sin n\theta$ for all $n \in \mathbb{N}$, stating clearly which trigonometric addition…
Let $z = \cos\theta + i\sin\theta$. Prove by induction that $z^n = \cos n\theta + i\sin n\theta$ for all $n \in \mathbb{N}$, stating clearly which trigonometric addition formulae you use. Hence evaluate $\left(\cos\frac{\pi}{12} + i\sin\frac{\pi}{12}\right)^{6}$.