Proof: Practice Questions

In a proof by mathematical induction for the statement \(P(n): \sum_{r=1}^{n} r = \frac{n(n+1)}{2}\), a student assumes \(P(k)\) is true for some positive integer \(k\). Which of the following expressions correctly shows the first step in evaluating the sum for \(n=k+1\) using the inductive hypothesis?

In a proof by mathematical induction that \(f(n) = 5^{2n} - 1\) is divisible by 24 for all \(n \in \mathbb{Z}^+\), a student considers the difference \(f(k+1) - f(k)\). Which of the following expressions correctly facilitates the inductive step?

A proof by induction for the \(n\)th derivative of \(y = x^2 e^x\) uses the hypothesis that \(\frac{d^k y}{dx^k} = [x^2 + 2kx + k(k-1)]e^x\). To prove the result for \(n=k+1\), the derivative of this expression is found. Which of the following represents the correct simplified expression for \(\frac{d^{k+1} y}{dx^{k+1}}\)?

A student is proving that \(7^n - 3^n\) is divisible by \(4\) for all \(n \in \mathbb{Z}^+\) using induction. Let \(f(n) = 7^n - 3^n\). If the student assumes \(f(k) = 4M\) for some integer \(M\), which of the following identifies a valid expression for \(f(k+1)\) that directly incorporates the inductive hypothesis?

In a proof of Bernoulli's inequality, \((1+x)^n \ge 1 + nx\) for \(x > -1\) and \(n \in \mathbb{Z}^+\), the inductive step involves multiplying the assumption for \(n=k\) by \((1+x)\). Which of the following correctly identifies the term that is discarded to complete the inequality \((1+x)^{k+1} \ge 1 + (k+1)x\)?

Prove by mathematical induction that \(4^n - 1\) is divisible by 3 for all positive integers \(n\).

Prove by mathematical induction that \(\sum_{r=1}^{n} r(r+1) = \frac{1}{3}n(n+1)(n+2)\) for all \(n \in \mathbb{Z}^+\).

A conjecture states that for \( n \ge 4 \), \( 2^n < n! \).
(a) Verify the base case for the smallest possible value of \( n \).
(b) Complete the inductive step to prove that if \( 2^k < k! \) for some integer \( k \ge 4 \), then \( 2^{k+1} < (k+1)! \).

A student is investigating the divisibility properties of the expression \( f(n) = 4^n + 2 \), where \( n \) is a positive integer.

(a) Verify that \( f(n) \) is divisible by 3 for \( n = 1 \) and \( n = 2 \).
(b) Use the principle of mathematical induction to prove that \( 4^n + 2 \) is divisible by 3 for all \( n \in \mathbb{Z}^+ \).

A sequence of sums is defined by \( S_n = \sum_{r=1}^{n} r(r!) \) for \( n \in \mathbb{Z}^+ \).

(a) Calculate the values of \( S_1 \), \( S_2 \) and \( S_3 \).
(b) Suggest a formula for \( S_n \) in terms of \( n \).
(c) Use the principle of mathematical induction to prove the formula suggested in part (b) for all positive integers \( n \).