Principle of Mathematical Induction

Mathematical induction effectively proves that a property is ———— by the set of natural numbers.

If $P(n)$ involves an inequality like $a_n < b_n$, the goal of the inductive step is to show:

Why can we not use induction to prove a statement for all negative integers $\dots, -3, -2, -1$ using the standard base case $n=1$?

If $P(n)$ is $n^2 + 100$, what is $P(k+1) - P(k)$?

Which of the following sets is induction most naturally performed on?

The Principle of Mathematical Induction is often described as a 'Bottom-Up' approach. What does this refer to?

If $P(n)$ is the statement $2^n < n!$, for which value of $n$ does the statement first become true?

Which of the following is a necessary condition for a statement $P(n)$ to be provable for all $n \in \mathbb{N}$ using the Principle of Mathematical Induction?

If $P(1)$ is true, and $P(k) \Rightarrow P(k+1)$ for all $k \in \mathbb{N}$, and $S = \{n \in \mathbb{N} : P(n) \text{ is true}\}$. What is the infimum of $S$?

In the context of PMI, if the set of counter-examples to $P(n)$ is non-empty, then it must have a smallest element. This is used to prove the validity of PMI by:

What is the common difference between terms in the sum $1 + 4 + 7 + \dots + (3n-2)$?

In the statement $P(n): 1 + 2 + 2^2 + \dots + 2^{n-1} = 2^n - 1$, what is the term for $n=3$ on the LHS?

If $P(n)$ is a statement such that $P(1)$ is true and $P(k) \implies P(k+1)$, then $P(n)$ is true for:

If $P(n): (2n+7) < (n+3)^2$ is true for $n=k$, then for $n=k+1$, the LHS becomes:

For all $n \in \mathbb{N}$, the sum $1 + \frac{1}{1+2} + \frac{1}{1+2+3} + \dots + \frac{1}{1+2+\dots+n}$ equals:

The sum of the first $n$ terms of the series $1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 + \dots + n(n+1)(n+2)$ is:

If $P(n)$ is the statement $n^3 + 2n$ is divisible by 3, then for $n=k+1$, the expression $(k+1)^3 + 2(k+1)$ can be written as $(k^3 + 2k) + X$. What is $X$?

Using the Principle of Mathematical Induction, $3^{2n+2} - 8n - 9$ is divisible by 64. For the base case $n=1$, the value is:

The sum of the series $1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \dots + n(n+1)$ is:

The sum $1 \cdot 2 + 2 \cdot 2^2 + 3 \cdot 2^3 + \dots + n \cdot 2^n$ is equal to:

Consider $P(n): 2 \cdot 7^n + 3 \cdot 5^n - 5$ is divisible by 24. What is the value of the expression for the base case $n=1$?

If $P(n)$ is the statement $2^{2n} - 1$, which of the following represents $P(k+1)$?

In a series $1 \cdot 3 + 2 \cdot 4 + 3 \cdot 5 + ...$, what is the expression for the $k^{th}$ term?

The inequality $n! > 2^n$ is true for all natural numbers $n$ greater than or equal to:

For every natural number $n$, the sum of the first $n$ terms of the series $1 + 2 + 2^2 + 2^3 + \dots$ is:

The expression $2 \cdot 7^n + 3 \cdot 5^n - 5$ is divisible by which of the following for all $n \in \mathbb{N}$?

For all natural numbers $n$, $5^n - 1$ is always divisible by:

In the proof of $P(n): n^3 + 2n$ is divisible by 3, the inductive step $(k+1)^3 + 2(k+1)$ is expanded to $k^3 + 3k^2 + 3k + 1 + 2k + 2$. Regrouping to find $P(k)$ gives $(k^3 + 2k) + (3k^2 + 3k + 3)$. The second term is divisible by 3 because:

When proving $P(n): n^2 < 2^n$ for $n \ge 5$, the inductive step $(k+1)^2 < 2^{k+1}$ requires showing $k^2 + 2k + 1 < 2 \cdot 2^k$. Since $k^2 < 2^k$, it suffices to show $2k + 1 < k^2$. For which values of $k$ is $k^2 - 2k - 1 > 0$ true?

For the statement $P(n): 4^n + 15n - 1$ is divisible by 9, if $4^k + 15k - 1 = 9m$, then $4^{k+1} + 15(k+1) - 1$ equals $4(9m - 15k + 1) + 15k + 14$. The coefficient of $k$ in the simplified expression is: