Define proof by induction .

Proof by induction establishes that a result holds for a whole set of integers, by showing that it holds for a starting integer and that whenever it holds for one integer it holds for the next. Those two facts together carry the result up through every integer from the starting one onwards.

Induction is often pictured as a row of dominoes. What does the picture say goes wrong if the base case is never checked?

Nothing ever starts falling: you have shown that each domino would knock over the next, but not that any of them falls in the first place. Without a base case the inductive step is a chain with nothing to set it going, so it proves nothing at all.

What four kinds of statement is induction the standard tool for?

Induction is the usual route for: a formula for the sum of a series a formula for a term of a recursive sequence an expression for a power of a matrix a claim that an expression is always divisible by a given number

A recursive sequence defines each term from the previous two terms. What changes in the basic step?

Two base cases are needed rather than one, so the formula has to be shown to work for both of the given starting terms. One would not be enough, because the recurrence cannot produce a term until two earlier ones are already known.

True or False? To show an expression is divisible by 6, it is enough to show it is divisible by 2 and by 3.

True. 2 and 3 share no factor, so anything divisible by both must carry both in its factorisation and is therefore a multiple of 6. The trick needs that: it fails for 4 and 6 against 24, since 12 is divisible by both and is not a multiple of 24.

A LevelFurther MathsEdexcelCore PureFlashcardsProofProof by Induction

Proof by Induction (Edexcel A Level Further Maths: Core Pure): Flashcards

Exam code: 9FM0

1/20

0Still learning

Know0

FrontIntro to Proof by Induction
Define proof by induction.

Was this flashcard helpful?

Cards in this collection (20)

Define proof by induction.
Proof by induction establishes that a result holds for a whole set of integers, by showing that it holds for a starting integer and that whenever it holds for one integer it holds for the next.
Those two facts together carry the result up through every integer from the starting one onwards.
Induction is often pictured as a row of dominoes. What does the picture say goes wrong if the base case is never checked?
Nothing ever starts falling: you have shown that each domino would knock over the next, but not that any of them falls in the first place.
Without a base case the inductive step is a chain with nothing to set it going, so it proves nothing at all.
Complete the four steps of a proof by induction, in order:
the $______$ step, showing the result holds for a starting value; the $______$ step, taking the result to hold for $n = k$ ; the $______$ step, deducing it for $n = k + 1$ ; and the conclusion step.
The completed steps are:
the basic step, showing the result holds for a starting value; the assumption step, taking the result to hold for $n = k$ ; the inductive step, deducing it for $n = k + 1$ ; and the conclusion step.
The assumption made in the second step is what the third step is entitled to use, and it is always needed somewhere in that deduction.
True or False?
The base case of a proof by induction is always $n = 1$ .
False.
The base case is whichever integer the statement is claimed from, and $n = 0$ is common.
Proving that $6^{n} + 13^{n + 1}$ is divisible by 7 for all $n \geq 0$ starts at $n = 0$ , where the expression is $14$ .
What work does the assumption step of an induction proof involve?
None beyond writing the assumption down: you take the result to be true for $n = k$ without proving anything.
Assuming it is not circular, because what the proof actually establishes is the conditional claim that if it holds at $k$ then it holds at $k + 1$ .
What four kinds of statement is induction the standard tool for?
Induction is the usual route for:
- a formula for the sum of a series
- a formula for a term of a recursive sequence
- an expression for a power of a matrix
- a claim that an expression is always divisible by a given number
Which values of $n$ does an induction proof of de Moivre's theorem establish it for?
The positive integers only.
Induction starts at a base case and moves up one whole step at a time, so it can never reach a value that is not a whole number of steps from where it began.
Complete the assumption step in the induction proof of de Moivre's theorem:
${[r (\cos θ + i \sin θ)]}^{k} =______(\cos k θ + i \sin k θ)$
The completed assumption is:
${[r (\cos θ + i \sin θ)]}^{k} = r^{k} (\cos k θ + i \sin k θ)$
The modulus is raised to the power while the argument is multiplied by it, and keeping those two behaviours apart is what the whole proof turns on.
Multiplying out the brackets in the inductive step of de Moivre's theorem gives four terms. What two facts turn them into the $n = k + 1$ form?
First $i^{2} = - 1$ , which flips the sign of the $\sin k θ \sin θ$ term and moves it into the real part.
Then the compound angle formulae, which recognise the real part as $\cos (k θ + θ)$ and the imaginary part as $\sin (k θ + θ)$ .
In a proof by induction about a recursive sequence, what gets you from $u_{k + 1}$ back to $u_{k}$ ?
The sequence's own recursive definition does, since that is what says how each term is built from the one before.
With $u_{n + 1} = 5 u_{n} - 4$ you write $u_{k + 1} = 5 u_{k} - 4$ , and only then substitute the assumed formula for $u_{k}$ .
A recursive sequence defines each term from the previous two terms. What changes in the basic step?
Two base cases are needed rather than one, so the formula has to be shown to work for both of the given starting terms.
One would not be enough, because the recurrence cannot produce a term until two earlier ones are already known.
Complete the identity that makes the inductive step work for a series:
$\sum_{r = 1}^{k + 1} f (r) =______+ \sum_{r = 1}^{k} f (r)$
The completed identity is:
$\sum_{r = 1}^{k + 1} f (r) = f (k + 1) + \sum_{r = 1}^{k} f (r)$
Splitting the last term off is what creates a sum running up to $k$ , which is the only thing the assumption can be substituted into.
What is a tidy way to organise the inductive step for a series?
Simplify the left-hand side and the right-hand side separately, then show that the two expressions are identical.
The right-hand side is only the given formula with $k + 1$ written in place of $n$ , so it can be written down and tidied before the left-hand side is touched at all.
After the assumption has been substituted, a series proof stands at $(k + 1) (k - 2) + \frac{1}{3} k (k - 4) (k + 1)$ . What is the next move?
Take out the common factor $\frac{1}{3} (k + 1)$ , leaving $\frac{1}{3} (k + 1) [3 (k - 2) + k (k - 4)]$ .
The bracket simplifies to $k^{2} - k - 6$ and factorises as $(k - 3) (k + 2)$ , which is the form the right-hand side needs.
Complete the way a divisibility assumption is written down:
The assumption that $f (k)$ is divisible by 7 is written $f (k) =______$ where $p$ is an $______$ to be carried through the proof.
The completed statement is:
The assumption that $f (k)$ is divisible by 7 is written $f (k) = 7 p$ where $p$ is an integer to be carried through the proof.
Turning the word divisible into an equation is what gives you something to substitute at the inductive step.
What is the key manipulation in the inductive step of a divisibility proof?
Peel one factor off each power, using $a^{k + 1} = a \times a^{k}$ , so that the terms of $f (k)$ begin to appear.
Rearranging the assumption then lets you replace one of those powers and take the divisor out as a factor of everything.
In proving $f (n) = 6^{n} + 13^{n + 1}$ is divisible by 7, how is the assumption $6^{k} + 13^{k + 1} = 7 p$ actually used?
Rearrange it to $6^{k} = 7 p - 13^{k + 1}$ and substitute that into $f (k + 1) = 6 (6^{k}) + 13 (13^{k + 1})$ .
Everything then collects as $7 (6 p + 13^{k + 1})$ , which is a multiple of 7 because the bracket is an integer.
True or False?
To show an expression is divisible by 6, it is enough to show it is divisible by 2 and by 3.
True.
2 and 3 share no factor, so anything divisible by both must carry both in its factorisation and is therefore a multiple of 6.
The trick needs that: it fails for 4 and 6 against 24, since 12 is divisible by both and is not a multiple of 24.
What is the key step when proving a formula for $M^{n}$ by induction?
Write $M^{k + 1} = M M^{k}$ and replace $M^{k}$ by the assumed matrix, which leaves an ordinary matrix multiplication to carry out.
The product then has to be shown to match the given formula with $k + 1$ written in place of $n$ .
The entries of $M^{k + 1}$ come out messy. How can the working be kept readable?
Write $M^{k + 1} = [\begin{matrix} a & b \\ c & d \end{matrix}]$ and then find each of $a$ , $b$ , $c$ and $d$ on a line of its own.
Each entry is a short calculation, so separating them stops a long expression having to be copied out four times over.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Previous:Simple Harmonic Motion