True or False? The basic step in proof by induction always uses n = 1 as the base case.

False. The basic step in proof by induction typically uses n = 1 or 0 as the base case, but it could be any integer.

What is the inductive step in a proof by induction.?

The inductive step is showing that if the result is true for n = k , then it is also true for n = k + 1 .

What are the four main steps in proof by induction?

The four main steps in proof by induction are: The basic step The assumption step The inductive step The conclusion step .

True or False? It is not always essential to complete the conclusion step when writing a proof by induction.

False. It is always essential to complete the conclusion step when writing a proof by induction. An induction proof without a conclusion is incomplete, and will lose marks.

True or False? In the conclusion step , you must state that the result is true for all integers greater than or equal to the base case .

True. In the conclusion step , you must state that the result is true for all integers greater than or equal to the base case .

What is the assumption step in a proof by induction?

The assumption step is assuming the result is true for n = k, for some integer k .

True or False? De Moivre's theorem can be proved using proof by induction ?

True. De Moivre's theorem is a theorem related to complex numbers that can be proved using proof by induction .

What is proof by contradiction ?

Proof by contradiction is a way of proving a result is true by showing that the negation (i.e. the 'opposite' of the result) cannot be true.

State the meaning of contradiction .

A contradiction is a logical inconsistency between two statements or results.

What are the three main steps in a proof by contradiction?

The three main steps in a proof by contradiction are: Assume the negation of the statement is true. Use the assumption in step 1 to find two results which contradict each other. Explain why the original statement is true.

True or False? To negate a statement with " all ", you replace it with " there is at least one ".

True. To negate a statement with " all ", you replace it with " there is at least one ".

State a method to prove by contradiction that there is no maximum multiple of 3.

To prove by contradiction that there is no maximum multiple of 3: Assume there is a maximum multiple of 3 called a , Then show that 3 a (or a +3) is a larger multiple of 3, which is a contradiction.

What is a method to prove by contradiction that n is even if n ² is even?

To prove by contradiction that n is even if n ² is even: Assume n ² is even and n is odd, Then use the assumption to show that n ² is odd (by squaring an expression for an odd number), which is a contradiction.

IBMathsDPAnalysis & Approaches (AA)HLFlashcards1. Number & AlgebraProof by Induction & Contradiction

Proof by Induction & Contradiction (DP IB Analysis & Approaches (AA))

Flashcards

1/20

FrontProof by Induction
What is proof by induction?
BackProof by Induction
Proof by induction is a method of proving a result is true, for a result that can be connected to the integers, usually $n = 1, 2, 3, . . .$ .
The statement is shown to be true for all possible values of $n$ by showing that:
If it is true for any one value of $n$ , it is also true for the next value of $n$ .
It is true when $n = 1$ .

Enjoying Flashcards?
Tell us what you think

Cards in this collection (20)

What is proof by induction?
Proof by induction is a method of proving a result is true, for a result that can be connected to the integers, usually $n = 1, 2, 3, . . .$ .
The statement is shown to be true for all possible values of $n$ by showing that:
- If it is true for any one value of $n$ , it is also true for the next value of $n$ .
- It is true when $n = 1$ .
True or False?
The basic step in proof by induction always uses n = 1 as the base case.
False.
The basic step in proof by induction typically uses n = 1 or 0 as the base case, but it could be any integer.
What is the inductive step in a proof by induction.?
The inductive step is showing that if the result is true for n = k, then it is also true for n = k + 1.
What are the four main steps in proof by induction?
The four main steps in proof by induction are:
1. The basic step
2. The assumption step
3. The inductive step
4. The conclusion step.
True or False?
It is not always essential to complete the conclusion step when writing a proof by induction.
False.
It is always essential to complete the conclusion step when writing a proof by induction.
An induction proof without a conclusion is incomplete, and will lose marks.
True or False?
In the conclusion step, you must state that the result is true for all integers greater than or equal to the base case.
True.
In the conclusion step, you must state that the result is true for all integers greater than or equal to the base case.
What is the assumption step in a proof by induction?
The assumption step is assuming the result is true for n = k, for some integer k.
What is a useful trick for the inductive step when dealing with sums of sequences?
A useful trick for the inductive step when dealing with sums of sequences is using the equation $\sum_{r = 1}^{k + 1} f (r) = f (k + 1) + \sum_{r = 1}^{k} f (r)$ .
What is a useful trick for the inductive step when dealing with derivatives?
A useful trick for the inductive step when dealing with derivatives is using the equation $f^{(k + 1)} (x) = \frac{d}{d x} f^{(k)} (x)$ .
I.e., the (k+1)th derivative is the derivative of the kth derivative.
What is a useful trick for the inductive step when dealing with divisibility proofs?
A useful trick for the inductive step when dealing with divisibility proofs is using the equation $a^{k + 1} = a \times a^{k}$
What is a useful trick for the inductive step when dealing with factorials?
A useful trick for the inductive step when dealing with factorials is using the equation $(k + 1)! = (k + 1) \times k!$ .
True or False?
De Moivre's theorem can be proved using proof by induction?
True.
De Moivre's theorem is a theorem related to complex numbers that can be proved using proof by induction.
What is proof by contradiction?
Proof by contradiction is a way of proving a result is true by showing that the negation (i.e. the 'opposite' of the result) cannot be true.
State the meaning of contradiction.
A contradiction is a logical inconsistency between two statements or results.
What are the three main steps in a proof by contradiction?
The three main steps in a proof by contradiction are:
1. Assume the negation of the statement is true.
2. Use the assumption in step 1 to find two results which contradict each other.
3. Explain why the original statement is true.
True or False?
To negate a statement with "all", you replace it with "there is at least one".
True.
To negate a statement with "all", you replace it with "there is at least one".
State a method to prove by contradiction that there is no maximum multiple of 3.
To prove by contradiction that there is no maximum multiple of 3:
- Assume there is a maximum multiple of 3 called a,
- Then show that 3a (or a+3) is a larger multiple of 3, which is a contradiction.
What is a method to prove by contradiction that n is even if n² is even?
To prove by contradiction that n is even if n² is even:
- Assume n² is even and n is odd,
- Then use the assumption to show that n² is odd (by squaring an expression for an odd number), which is a contradiction.
What is a common method to prove that $\sqrt{n}$ is irrational when $n$ is prime?
A common method to prove that $\sqrt{n}$ is irrational when $n$ is prime is to:
- assume $\sqrt{n} = \frac{a}{b}$ where $a$ and $b$ are integers with no common factors and $b \neq 0$ ,
- then use algebra to show that $n$ is a factor of both $a$ and $b$ (this contradicts the assumption that $a$ and $b$ have no common factors).
What is a common method to prove that there is an infinite number of prime numbers?
A common method to prove that there is an infinite number of prime numbers is to:
- assume there are only $n$ primes $p_{1}, p_{2}, . . ., p_{n}$ ,
- then show that $p = 1 + (p_{1} \times p_{2} \times \dots \times p_{n})$ is a prime that is bigger than any of the $n$ primes.

1. Number & Algebra

2. Functions

3. Geometry & Trigonometry

4. Statistics & Probability

5. Calculus