9231 · 1.7
Proof by induction flashcards
Revision flashcards for Cambridge 9231 Proof by induction (syllabus 1.7). Flip, recall, then mark a real past-paper question.
Card
What is the principle of mathematical induction?
A method to prove a statement $P(n)$ is true for all integers $n \ge n_0$ by showing $P(n_0)$ is true (base case) and that for any $k \ge n_0$, if $P(k)$ is true, then $P(k+1)$ is also true (inductive step).
Card
What is the 'Base Case' in a proof by induction?
The first step, where you prove the statement is true for the smallest integer value specified in the question, e.g., $n=1$.
Card
What is the 'Inductive Hypothesis'?
The assumption that the statement is true for an arbitrary integer $k$, i.e., assuming $P(k)$ is true. This is a crucial step before proving for $k+1$.
Card
What is the goal of the 'Inductive Step'?
To show that if the statement is true for $n=k$, it must also be true for $n=k+1$. You must use the inductive hypothesis to achieve this.
Card
Why is the concluding statement so important?
It formally links the base case and the inductive step to the principle of mathematical induction, completing the logical argument. A proof without it is incomplete and will lose marks.
Card
Common mistake: Proving $P(k+1)$ without using the assumption $P(k)$. Why is this wrong?
The logic of induction rests on the 'if $P(k)$ then $P(k+1)$' link. If you don't use the assumption $P(k)$, you haven't shown this connection, and your proof is invalid.
Card
How do you start the inductive step for a summation, e.g., $\sum_{r=1}^{n} f(r)$?
Write out the sum for $n=k+1$: $\sum_{r=1}^{k+1} f(r) = (\sum_{r=1}^{k} f(r)) + f(k+1)$. Then substitute the assumed formula for the sum to $k$.
Card
How do you approach a divisibility proof, e.g., 'prove $f(n)$ is divisible by $d$'?
Assume $f(k) = dm$ for some integer $m$. Then analyse $f(k+1)$ and manipulate it to show it is also a multiple of $d$. A common technique is to consider $f(k+1) - f(k)$.
Card
What if the base case is not $n=1$?
The base case is the first integer for which the statement is claimed to be true. This could be $n=0$, $n=2$, or any other integer $n_0$. The conclusion would then be 'true for all integers $n \ge n_0$'.
Card
How do you prove a statement involving matrices, like $\mathbf{A}^n = \mathbf{B}_n$, by induction?
Base case: Show $\mathbf{A}^1 = \mathbf{B}_1$. Assumption: Assume $\mathbf{A}^k = \mathbf{B}_k$. Inductive step: Prove $\mathbf{A}^{k+1} = \mathbf{B}_{k+1}$ by writing $\mathbf{A}^{k+1} = \mathbf{A}^k \mathbf{A}$ and substituting the assumption: $\mathbf{B}_k \mathbf{A}$. Then show this product equals $\mathbf{B}_{k+1}$.