Mathematical Induction: Proof Technique

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Prove, using mathematical induction, that for all $n ≥ 1$, the sum of the cubes of the first $n$ natural numbers is equal to $(n(n+1)/2)^2$.

Basis step: For $n=1$, $1^3 = (1(1+1)/2)^2 = 1$. Inductive hypothesis: Assume $\sum_{i=1}^{k} i^3 = (k(k+1)/2)^2$. Inductive step: Show $\sum_{i=1}^{k+1} i^3 = ((k+1)(k+2)/2)^2$. $\sum_{i=1}^{k+1} i^3 = (k(k+1)/2)^2 + (k+1)^3 = (k+1)^2[k^2/4 + k + 1] = (k+1)^2(k^2 + 4k + 4)/4 = ((k+1)(k+2)/2)^2$.

Use mathematical induction to prove that $n^3 - n$ is divisible by 3 for all integers $n ≥ 0$.

Basis step: For $n=0$, $0^3 - 0 = 0$, which is divisible by 3. Inductive hypothesis: Assume $k^3 - k$ is divisible by 3. Inductive step: Show $(k+1)^3 - (k+1)$ is divisible by 3. $(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3(k^2 + k)$. Since $k^3 - k$ is divisible by 3 (by the inductive hypothesis) and $3(k^2 + k)$ is also divisible by 3, their sum is divisible by 3.

Prove by mathematical induction that for all $n ≥ 1$, $1/(12) + 1/(23) + ... + 1/(n(n+1)) = n/(n+1)$.

Basis step: For $n=1$, $1/(1*2) = 1/2 = 1/(1+1)$. Inductive hypothesis: Assume $\sum_{i=1}^{k} 1/(i(i+1)) = k/(k+1)$. Inductive step: Show $\sum_{i=1}^{k+1} 1/(i(i+1)) = (k+1)/(k+2)$. $\sum_{i=1}^{k+1} 1/(i(i+1)) = k/(k+1) + 1/((k+1)(k+2)) = [k(k+2) + 1]/((k+1)(k+2)) = (k^2 + 2k + 1)/((k+1)(k+2)) = (k+1)^2/((k+1)(k+2)) = (k+1)/(k+2)$.

Use mathematical induction to prove that for $n ≥ 5$, $2^n > n^2$.

Basis step: For $n=5$, $2^5 = 32 > 5^2 = 25$. Inductive hypothesis: Assume $2^k > k^2$ for some $k ≥ 5$. Inductive step: Show $2^(k+1) > (k+1)^2$. $2^(k+1) = 2 * 2^k > 2 * k^2 = k^2 + k^2$. Since $k ≥ 5$, $k^2 > 2k + 1$. Thus, $2^(k+1) > k^2 + 2k + 1 = (k+1)^2$. Signup and view all the answers

Prove that the recurrence relation $F(n) = F(n-1) + F(n-2)$ with $F(0) = 0$ and $F(1) = 1$ has the closed-form solution $F(n) = (φ^n - (-φ)^{-n}) / √5$, where $φ = (1 + √5) / 2$ (the golden ratio).

Basis step: For $n=0$, $F(0) = (φ^0 - (-φ)^0) / √5 = (1 - 1) / √5 = 0$. For $n=1$, $F(1) = (φ - (-φ)^{-1}) / √5 = (φ + 1/φ) / √5 = ((1 + √5)/2 + 2/(1 + √5)) / √5 = ((1 + √5)/2 + (2(√5 - 1))/(5 - 1)) / √5 = √5/√5 = 1$. Inductive hypothesis: Assume the formula holds for all $i ≤ k$. Inductive step: Show it holds for $k+1$. $F(k+1) = F(k) + F(k-1) = (φ^k - (-φ)^{-k}) / √5 + (φ^(k-1) - (-φ)^(-(k-1))) / √5 = (φ^(k-1)(φ + 1) - (-φ)^(-(k+1))( (-φ)^2 + (-φ)) /√5$. Since $\phi + 1 = \phi^2$ and $(-φ)^2 - φ$ simplifies we eventually arrive at $(φ^(k+1) - (-φ)^(-(k+1))) / √5$. Signup and view all the answers

Using mathematical induction, show that any set with $n$ elements has $2^n$ subsets.

Basis step: For $n=0$, the set is empty ({}). The number of subsets is one: {}. Since $2^0 = 1$, the statement holds. Inductive hypothesis: Assume a set with $k$ elements has $2^k$ subsets. Inductive step: Consider a set with $k+1$ elements. We can create this set by starting with a set of $k$ elements and adding one new element, $x$. All subsets of the original set of $k$ elements are subsets of the new set. Also, for each subset of the original set, we can create a new subset by adding $x$ to it. This doubles the number of subsets. Therefore, a set with $k+1$ elements has $2 * 2^k = 2^(k+1)$ subsets. Signup and view all the answers

Prove by mathematical induction that for all $n ≥ 1$, $1^2 + 3^2 + 5^2 + ... + (2n-1)^2 = n(2n-1)(2n+1)/3$.

Basis step: For $n=1$, $1^2 = 1(21-1)(21+1)/3 = 1$. Inductive hypothesis: Assume $\sum_{i=1}^{k} (2i-1)^2 = k(2k-1)(2k+1)/3$. Inductive step: Show $\sum_{i=1}^{k+1} (2i-1)^2 = (k+1)(2(k+1)-1)(2(k+1)+1)/3$. $\sum_{i=1}^{k+1} (2i-1)^2 = k(2k-1)(2k+1)/3 + (2(k+1)-1)^2 = k(4k^2 - 1)/3 + (2k+1)^2 = (4k^3 - k + 12k^2 + 12k + 3)/3 = (4k^3 + 12k^2 + 11k + 3)/3 = (k+1)(2k+1)(2k+3)/3 = (k+1)(2(k+1)-1)(2(k+1)+1)/3$. Signup and view all the answers

Define a sequence by $a_1 = 1$ and $a_{n+1} = 3a_n + 1$ for $n ≥ 1$. Prove, using mathematical induction, that $a_n = (3^n - 1) / 2$ for all $n ≥ 1$.

Basis step: For $n=1$, $a_1 = (3^1 - 1) / 2 = 1$. Inductive hypothesis: Assume $a_k = (3^k - 1) / 2$. Inductive step: Show $a_{k+1} = (3^(k+1) - 1) / 2$. $a_{k+1} = 3a_k + 1 = 3((3^k - 1) / 2) + 1 = (3^(k+1) - 3) / 2 + 1 = (3^(k+1) - 3 + 2) / 2 = (3^(k+1) - 1) / 2$. Signup and view all the answers

Prove, using strong induction, that every integer $n > 1$ can be written as a product of prime numbers. (Note: A single prime number is considered a product of prime numbers.)

Basis step: For $n=2$, 2 is a prime number, so it can be written as a product of itself. Inductive hypothesis: Assume that all integers $2 ≤ j ≤ k$ can be written as a product of primes. Inductive step: Consider $k+1$. If $k+1$ is prime, then it is a product of primes. If $k+1$ is composite, then $k+1 = ab$ where $1 < a, b < k+1$. Then $2 ≤ a, b ≤ k$, so by the inductive hypothesis, $a$ and $b$ can each be written as a product of primes. Therefore, $k+1 = ab$ can be written as a product of primes as well. Signup and view all the answers

Consider the Fibonacci sequence defined by $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n ≥ 2$. Prove by induction that $\sum_{i=0}^{n} F_i^2 = F_n * F_{n+1}$ for all $n ≥ 0$.

Basis step: For $n=0$, $\sum_{i=0}^{0} F_i^2= 0^2 = 0$. Also, $F_0F_1 = 0 * 1 = 0$. Inductive hypothesis: Assume that $\sum_{i=0}^{k} F_i^2 = F_k * F_{k+1}$. Inductive step: Show $\sum_{i=0}^{k+1} F_i^2 = F_{k+1} * F_{k+2}$. $\sum_{i=0}^{k+1} F_i^2 = \sum_{i=0}^{k} F_i^2 + F_{k+1}^2 = F_k * F_{k+1} + F_{k+1}^2 = F_{k+1}(F_k + F_{k+1}) = F_{k+1}*F_{k+2}$. Signup and view all the answers

Flashcards

Mathematical Induction

A method of mathematical proof used to establish a statement for all natural numbers greater than or equal to some initial value.

Basis Step

Prove the statement is true for the initial value (usually n = 1).

Inductive Step

Assume the statement is true for an arbitrary natural number k (the inductive hypothesis), then prove it's true for k + 1.

Inductive Hypothesis

The assumption that P(k) is true for some arbitrary integer k greater than or equal to the initial value.