IB Mathematics: Analysis and Approaches Quiz: Proof By Induction And Contradiction

A sequence is defined by $a_1=2, a_2=3$ and $a_n = a_{n-1} + 2a_{n-2}$ for $n \ge 3$. A proof by induction is used to show that $a_n = 2^n + (-1)^n$ for all $n \in \mathbb{Z}^+$. Why is a standard inductive hypothesis (assuming the proposition is true for $n=k$) insufficient for the inductive step?

Let $P(n)$ be the proposition that $8^n - 3^n$ is divisible by 5. In the inductive step, assuming $P(k)$ is true, we consider $8^{k+1} - 3^{k+1}$. Which of the following expressions is a valid manipulation that helps to complete the proof?

A sequence is defined by $a_1=2, a_2=3$ and $a_n = a_{n-1} + 2a_{n-2}$ for $n \ge 3$. A proof by induction is used to show that $a_n = 2^n + (-1)^n$ for all $n \in \mathbb{Z}^+$. Why is a standard inductive hypothesis (assuming the proposition is true for $n=k$) insufficient for the inductive step?

Let $P(n)$ be a statement about a positive integer $n$. It is found that $P(50)$ is true. It is also proven that for any integer $k > 1$, the truth of $P(k)$ implies the truth of $P(k-1)$. What is the strongest conclusion that can be made?

In a proof by induction for the statement $S(n): \sum_{i=1}^{n} i(i+1) = \frac{n(n+1)(n+2)}{3}$ for $n \in \mathbb{Z}^+$, the inductive step requires proving that if $S(k)$ is true for some $k \in \mathbb{Z}^+$, then $S(k+1)$ is true. Which of the following equations must be established to complete this inductive step?

Let $P(n)$ be a statement to be proven by induction for $n \in \mathbb{Z}^+$. If the base case $P(1)$ is false, but the inductive step (that is, $P(k) \implies P(k+1)$ for all $k \ge 1$) is proven to be valid, what can be concluded?

A student presents the following flawed proof that all horses are the same color.

Base Case: For $n=1$, in any set containing one horse, all horses in that set are the same color. This is true.

Inductive Step: Assume for any set of $k$ horses, all horses have the same color. Consider a set of $k+1$ horses. Remove the first horse; the remaining $k$ horses have the same color by the inductive hypothesis. Put the first horse back and remove the last horse; this set of $k$ horses also has the same color. Therefore, the first horse has the same color as the middle horses, which in turn have the same color as the last horse. Thus, all $k+1$ horses have the same color.

The reasoning in the inductive step is flawed. For which value of $k$ does the argument fail?

In the proof of De Moivre's theorem by induction, $(\cos\theta + i\sin\theta)^n = \cos(n\theta) + i\sin(n\theta)$, the inductive step involves expanding $(\cos(k\theta) + i\sin(k\theta))(\cos\theta + i\sin\theta)$. After expansion, what is the real part of the resulting complex number?

A student attempts to prove that if $ab$ is an irrational number, then either $a$ or $b$ is irrational. The student writes: 'Assume $a$ and $b$ are both rational. Let $a = p/q$ and $b = r/s$ for integers $p, q, r, s$. Then $ab = pr/qs$, which is rational. This contradicts the fact that the product of two rationals must be irrational.' Besides the error in the final sentence, what is the primary logical issue with this argument as a proof by contradiction?

In the standard proof by contradiction that $\sqrt{5}$ is irrational, we assume $\sqrt{5} = \frac{p}{q}$ where $p, q \in \mathbb{Z}$ and the fraction is in its simplest form (i.e., $\gcd(p,q)=1$). The proof leads to the conclusion that both $p$ and $q$ must be multiples of 5. What is the primary contradiction reached at this point?

To prove that there are infinitely many prime numbers, the proof by contradiction begins by assuming there is a finite number of primes, $p_1, p_2, \dots, p_n$. A new number $N = p_1 p_2 \dots p_n + 1$ is constructed. The argument then states that $N$ must have a prime factor. What contradiction is ultimately reached?

In a proof by mathematical induction for a statement $P(n)$, it is shown that $P(2)$ is true. It is also shown that for any integer $k \ge 2$, the truth of $P(k)$ implies the truth of $P(k+2)$. What can be concluded?

Let $M = \begin{pmatrix} 3 & -4 \\ 1 & -1 \end{pmatrix}$. It is proposed that $M^n = \begin{pmatrix} 2n+1 & -4n \\ n & 1-2n \end{pmatrix}$ for $n \in \mathbb{Z}^+$. In the inductive step, assuming the formula is true for $n=k$, we compute $M^{k+1} = M^k M$. What is the entry in the first row, first column of the resulting matrix $M^{k+1}$?

Let $P(n)$ be a statement to be proven by induction for $n \in \mathbb{Z}^+$. If the base case $P(1)$ is false, but the inductive step (that is, $P(k) \implies P(k+1)$ for all $k \ge 1$) is proven to be valid, what can be concluded?

In the standard proof by contradiction that $\sqrt{5}$ is irrational, we assume $\sqrt{5} = \frac{p}{q}$ where $p, q \in \mathbb{Z}$ and the fraction is in its simplest form (i.e., $\gcd(p,q)=1$). The proof leads to the conclusion that both $p$ and $q$ must be multiples of 5. What is the primary contradiction reached at this point?

To prove that there are infinitely many prime numbers, the proof by contradiction begins by assuming there is a finite number of primes, $p_1, p_2, \dots, p_n$. A new number $N = p_1 p_2 \dots p_n + 1$ is constructed. The argument then states that $N$ must have a prime factor. What contradiction is ultimately reached?

In a proof by mathematical induction for a statement $P(n)$, it is shown that $P(2)$ is true. It is also shown that for any integer $k \ge 2$, the truth of $P(k)$ implies the truth of $P(k+2)$. What can be concluded?

Let $M = \begin{pmatrix} 3 & -4 \\ 1 & -1 \end{pmatrix}$. It is proposed that $M^n = \begin{pmatrix} 2n+1 & -4n \\ n & 1-2n \end{pmatrix}$ for $n \in \mathbb{Z}^+$. In the inductive step, assuming the formula is true for $n=k$, we compute $M^{k+1} = M^k M$. What is the entry in the first row, first column of the resulting matrix $M^{k+1}$?

To prove that $\log_3 10$ is irrational by contradiction, one assumes $\log_3 10 = \frac{p}{q}$ for integers $p, q$ with $q ≠ 0$. Rewriting this gives $3^{p/q} = 10$, or $3^p = 10^q$. Why does this final equation represent a contradiction for positive integers $p$ and $q$?

A student is proving by induction that $\sum_{r=1}^{n} r^3 = \left( \frac{n(n+1)}{2} \right)^2$. They correctly assume the formula for $n=k$. Which expression correctly represents the value that must be added to $\left( \frac{k(k+1)}{2} \right)^2$ to begin the proof for $n=k+1$?