Subjects algebra

Induction Proofs

Step-by-step solutions with LaTeX - clean, fast, and student-friendly.

Search Solutions

Induction Proofs


1. **Prove by induction that** $a + ar + \cdots + ar^{n-1} = a \frac{1-r^n}{1-r}$ for $r \neq 1$. Step 1: Base case ($n=1$): LHS = $a$, RHS = $a \frac{1 - r^1}{1 - r} = a \frac{1 - r}{1 - r} = a$. Base case holds. Step 2: Inductive hypothesis: Assume formula holds for $n=k$, i.e. $$a + ar + \cdots + ar^{k-1} = a \frac{1-r^k}{1-r}.$$ Step 3: Inductive step: For $n=k+1$, LHS = $$a + ar + \cdots + ar^{k-1} + ar^k.$$ Using hypothesis, LHS = $$a \frac{1-r^k}{1-r} + ar^k = \frac{a(1-r^k)}{1-r} + ar^k = \frac{a(1-r^k) + ar^k(1-r)}{1-r}.$$ Simplify numerator: $$a(1-r^k) + ar^k - ar^{k+1} = a + ar^k - ar^k - ar^{k+1} = a - ar^{k+1}.$$ So, LHS = $$\frac{a(1-r^{k+1})}{1-r},$$ which equals RHS for $n=k+1$. Induction holds. 2. **Prove by induction that** $1^2 + 3^2 + 5^2 + \cdots + (2n-1)^2 = \frac{1}{3} n (4n^2 - 1)$. Step 1: Base case ($n=1$): LHS = $1^2=1$, RHS = $\frac{1}{3} \times 1 \times (4 - 1) = \frac{1}{3} \times 3 = 1$. Base case holds. Step 2: Inductive hypothesis: Assume true for $n=k$, so $$1^2 + 3^2 + \cdots + (2k-1)^2 = \frac{1}{3} k (4k^2 -1).$$ Step 3: Inductive step: For $n=k+1$, LHS = $$\left(1^2 + 3^2 + \cdots + (2k-1)^2\right) + (2(k+1)-1)^2 = \frac{1}{3} k (4k^2 -1) + (2k+1)^2.$$ Expand and simplify: $\frac{1}{3}k(4k^2 -1) + (2k+1)^2 = \frac{1}{3}k(4k^2 -1) + 4k^2 + 4k +1.$ Rewrite $4k^2 + 4k +1$ as $\frac{12k^2 + 12k + 3}{3}$ and combine: $$\frac{1}{3}k(4k^2 -1) + \frac{12k^2 + 12k +3}{3} = \frac{4k^3 - k + 12k^2 + 12k + 3}{3} = \frac{4k^3 + 12k^2 + 11k + 3}{3}.$$ Right side formula for $n=k+1$ is $$\frac{1}{3} (k+1) (4(k+1)^2 -1) = \frac{1}{3} (k+1)(4k^2 + 8k + 4 -1) = \frac{1}{3}(k+1)(4k^2 + 8k + 3).$$ Expand: $$\frac{1}{3}(4k^3 + 8k^2 + 3k + 4k^2 + 8k +3) = \frac{1}{3}(4k^3 + 12k^2 + 11k + 3),$$ which matches LHS. Inductive step holds. 3. **Prove by induction that** $4^2 + 7^2 + 10^2 + \cdots + (3n + 1)^2 = \frac{1}{2} n (6n^2 + 19n + 13)$ (given formula truncated, we finish assuming the RHS as stated). Step 1: Base case ($n=1$): LHS = $4^2=16$, RHS = $\frac{1}{2} \times 1 \times (6 + 19 + 13) = \frac{1}{2} \times 38 = 19$. Since $16 \neq 19$, verify formula or redefine as: assume RHS = $\frac{1}{2} n (6n^2 + 19n + 13)$ is correct to show method. Step 2: Inductive hypothesis: Assume true for $n=k$, $$4^2 + 7^2 + \cdots + (3k +1)^2 = \frac{1}{2} k (6k^2 + 19k + 13).$$ Step 3: Inductive step: For $n=k+1$, LHS = $$\frac{1}{2} k (6k^2 + 19k + 13) + (3(k+1)+1)^2 = \frac{1}{2} k (6k^2 + 19k + 13) + (3k + 4)^2.$$ Expand $(3k+4)^2 = 9k^2 + 24k + 16$. So LHS = $$\frac{1}{2} k (6k^2 + 19k + 13) + 9k^2 + 24k + 16 = \frac{1}{2} k (6k^2 + 19k + 13) + \frac{18k^2 + 48k + 32}{2}.$$ Sum: $$\frac{1}{2} (6k^3 + 19k^2 + 13k + 18k^2 + 48k + 32).$$ Combine like terms: $$\frac{1}{2} (6k^3 + 37k^2 + 61k + 32).$$ RHS for $n=k+1$: $$\frac{1}{2} (k+1)(6(k+1)^2 + 19(k+1) + 13).$$ Expand inside: $$6(k^2 + 2k + 1) + 19k + 19 + 13 = 6k^2 + 12k + 6 + 19k + 19 + 13 = 6k^2 + 31k + 38.$$ Multiply out: $$\frac{1}{2} (k+1)(6k^2 + 31k + 38) = \frac{1}{2} (6k^3 + 31k^2 + 38k + 6k^2 + 31k + 38) = \frac{1}{2} (6k^3 + 37k^2 + 69k + 38).$$ Check equality with LHS: LHS has $\frac{1}{2} (6k^3 + 37k^2 + 61k + 32)$ vs RHS $\frac{1}{2} (6k^3 + 37k^2 + 69k + 38)$. They differ, so given formula likely truncated or misstated. Inductive proof method demonstrated here assuming correct formula. --- **Final answers:** 1. Proven: $$a + ar + \cdots + ar^{n-1} = a \frac{1-r^n}{1-r}.$$ 2. Proven: $$1^2 + 3^2 + \cdots + (2n-1)^2 = \frac{1}{3} n (4n^2 - 1).$$ 3. Shown induction steps with noted formula inconsistency, method demonstrated.