Basic Mathematical Induction - Flashcard set - Number Theory

Still learning

Prove by induction that for all integers $n\ge0$ , the sum of the first $n$ even natural numbers is $n(n+1)$ .

1. Base Case: Check the sum of the first 0 even natural numbers is $0(0+1)$ . 2. Inductive Step: Assume true for $n=k$ and prove for $n=k+1$ . 3. Show that $k(k+1) + 2(k+1) = (k+1)(k+2)$ .

Prove by induction that the number of subsets of a set with $n$ elements, for $n\ge0$ , is $2^n$ .

1. Base Case: Verify a set with 0 elements has $2^0$ subsets. 2. Inductive Step: Assume true for $n=k$ and prove for $n=k+1$ . 3. Argue that adding a new element doubles the number of subsets.

Prove by induction that $11^n - 6$ is divisible by 5 for all natural numbers $n$ .

1. Base Case: Check $11^1 - 6$ for divisibility by 5. 2. Inductive Step: Assume true for $n=k$ and prove for $n=k+1$ . 3. Express $11^{k+1} - 6$ in terms of $11^k - 6$ and factor to show divisibility.

Prove by induction that the factorial of any natural number $n$ is given by $n! = n \cdot (n-1)!$ with $1! = 1$ .

1. Base Case: Check $2! = 2 \cdot 1!$ . 2. Inductive Step: Assume true for $n=k$ and prove for $n=k+1$ . 3. Show that $(k+1)! = (k+1) \cdot k!$ and use the assumption.

Prove by induction that the sum of the first $n$ natural numbers is $\frac{n(n+1)}{2}$

1. Base Case: Prove the statement for $n = 1$ . 2. Inductive Step: Assume true for $n=k$ and prove for $n=k+1$ . 3. Show that $\frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}$ .

Prove by induction that for all $n\ge1$ , $1^2 + 2^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}$ .

1. Base Case: Check $1^2 = \frac{1(1+1)(2\cdot1+1)}{6}$ . 2. Inductive Step: Assume true for $n=k$ and prove for $n=k+1$ . 3. Add $(k+1)^2$ to both sides of the assumption and simplify.

Prove by induction that $\sum_{i=1}^{n} i^3 = \left(\frac{n(n+1)}{2}\right)^2$ for all $n \ge 1$ .

1. Base Case: Verify $1^3 = \left(\frac{1(1+1)}{2}\right)^2$ . 2. Inductive Step: Assume true for $n=k$ and prove for $n=k+1$ . 3. Add $(k+1)^3$ to both sides of the assumption and show it equals $\left(\frac{(k+1)(k+2)}{2}\right)^2$ .

Prove by induction that the number of diagonals in a polygon with $n$ sides, $n \ge 3$ , is given by $\frac{n(n-3)}{2}$ .

1. Base Case: Confirm a triangle (3 sides) has 0 diagonals. 2. Inductive Step: Assume true for $n=k$ and prove for $n=k+1$ . 3. Show that $\frac{k(k-3)}{2} + (k-2) = \frac{(k+1)(k-2)}{2}$ .

Prove by induction that $n^3 - n$ is divisible by 3 for every natural number n.

1. Base Case: Verify $1^3 - 1$ is divisible by 3. 2. Inductive Step: Assume true for $n=k$ and prove for $n=k+1$ . 3. Show that $(k+1)^3 - (k+1)$ can be written as a multiple of 3 plus $k^3 - k$ .

Prove by induction that for all $n\ge1$ , $2^n > n^2$

1. Base Case: Show $2^1 > 1^2$ . 2. Inductive Step: Assume true for $n=k$ and prove for $n=k+1$ . 3. Establish that if $2^k > k^2$ , then $2^{k+1} > (k+1)^2$ given that $k+1 > 2$ .

Prove by induction that the $n$ -th Fibonacci number $F_n$ is given by $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0$ and $F_1 = 1$ for all $n \ge 2$ .

1. Base Case: Verify $F_2 = F_1 + F_0$ . 2. Inductive Step: Assume true for $n=k$ and $n=k-1$ , then prove for $n=k+1$ . 3. Use the assumption to show $F_{k+1} = F_k + F_{k-1}$ .

Prove by induction that the $n$ -th term of the arithmetic sequence given by $a_n = 5n + 3$ is divisible by $5$ for $n\ge1$ .

1. Base Case: Check that $a_1 = 5\cdot1 + 3$ is divisible by $5$ . 2. Inductive Step: Assume true for $n=k$ and prove for $n=k+1$ . 3. Show that $5(k+1) + 3$ has the same divisibility by $5$ as $5k + 3$ .

Prove by induction that for all integers $n\ge2$ , the inequality $n! > 2^n$ holds.

1. Base Case: Verify that $2! > 2^2$ . 2. Inductive Step: Assume true for $n=k$ and prove for $n=k+1$ . 3. Use the assumption that $k! > 2^k$ to show $(k+1)! > 2^{k+1}$ for $k \ge 2$ .

Prove by induction that for every natural number $n\ge 4$ , the inequality $2^n > n^3$ holds.

1. Base Case: Check that $2^4 > 4^3$ . 2. Inductive Step: Assume true for $n=k$ and prove for $n=k+1$ . 3. Use the assumption to prove $2^{k+1} > (k+1)^3$ for $k \ge 4$ .

Prove by induction that for all $n \ge 1$ , $6$ divides $n^3 - n$ .

1. Base Case: Confirm that $6$ divides $1^3 - 1$ . 2. Inductive Step: Assume true for $n=k$ and prove for $n=k+1$ . 3. Express $k^3 - k$ as a sum of multiples of 6 and show $(k+1)^3 - (k+1)$ also has this property.

Know

Discover published sets by community