Exercises: Induction: identities and divisibility
Prove by induction that for all $n\in\mathbb{N}$, $$1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}.$$
Prove by induction that for all $n\in\mathbb{N}$,
$$1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}.$$Prove by induction that $\sum_{r=1}^{n} (2r-1) = n^2$ for all $n \in \mathbb{N}$.
Prove by induction that $\sum_{r=1}^{n} (2r-1) = n^2$ for all $n \in \mathbb{N}$.
Prove by induction that $4^n - 1$ is divisible by 3 for all $n\in\mathbb{N}$.
Prove by induction that $4^n - 1$ is divisible by 3 for all $n\in\mathbb{N}$.
Prove by induction that $$\sum_{r=1}^{n} r^2 = \frac{n(n+1)(2n+1)}{6}$$ for all $n\in\mathbb{N}$.
Prove by induction that
$$\sum_{r=1}^{n} r^2 = \frac{n(n+1)(2n+1)}{6}$$for all $n\in\mathbb{N}$.
Prove by induction that $\sum_{r=1}^{n} r\cdot 2^{r} = (n-1)2^{n+1} + 2$ for all $n\in\mathbb{N}$.
Prove by induction that $\sum_{r=1}^{n} r\cdot 2^{r} = (n-1)2^{n+1} + 2$ for all $n\in\mathbb{N}$.
Prove by induction that $7^n - 3^n$ is divisible by 4 for all $n \in \mathbb{N}$.
Prove by induction that $7^n - 3^n$ is divisible by 4 for all $n \in \mathbb{N}$.
Prove by induction that $$\sum_{r=1}^{n} \frac{1}{r(r+1)} = \frac{n}{n+1}$$ for all $n\in\mathbb{N}$. Hence evaluate $\sum_{r=1}^{\infty} \frac{1}{r(r+1)}$, justifying…
Prove by induction that
$$\sum_{r=1}^{n} \frac{1}{r(r+1)} = \frac{n}{n+1}$$for all $n\in\mathbb{N}$. Hence evaluate $\sum_{r=1}^{\infty} \frac{1}{r(r+1)}$, justifying your answer.
Prove by induction that $n^3 + 2n$ is divisible by 3 for all $n\in\mathbb{N}$, and that $5^{2n} - 1$ is divisible by 24 for all $n\in\mathbb{N}$.
Prove by induction that $n^3 + 2n$ is divisible by 3 for all $n\in\mathbb{N}$, and that $5^{2n} - 1$ is divisible by 24 for all $n\in\mathbb{N}$.
A sequence is defined by $u_1 = 1$, $u_2 = 5$ and $u_{n+2} = 5u_{n+1} - 6u_n$. a) Calculate $u_3$ and $u_4$. b) Conjecture a formula for $u_n$ in terms of powers of 2…
A sequence is defined by $u_1 = 1$, $u_2 = 5$ and $u_{n+2} = 5u_{n+1} - 6u_n$.
- a) Calculate $u_3$ and $u_4$.
- b) Conjecture a formula for $u_n$ in terms of powers of 2 and 3.
- c) Prove your formula by induction (strong induction on two previous terms).