Chapter 5.2 & 5.3 - Weak Induction

Front 1

Mathematical induction is used to check conjectures about the outcomes of processes that occur repeatedly and according to definite ________.

Back 1

definite patterns

Front 2

In general, mathematical induction is a method for proving that a property defined for integers n is true for ____ values of n that are greater than or equal to some initial integer.

Back 2

true for all values of n that are greater than or equal to some initial integer.

Front 3

Principle of Mathematical __________

Let P(n) be a property that is defined for integers n, and let a be a fixed integer. Suppose the following two statements are true: 1. P(a) is true. 2. For all integers k≥a, if P(k) is true then P(k + 1) is true. Then the statement for all integers n≥a, P(n) is true.

Back 3

Mathematical Induction

Front 4

Principle of Mathematical Induction Let P(n) be a property that is defined for integers n, and let a be a fixed integer. Suppose___________________.

Then the statement for all integers n≥a, P(n) is true.

Back 4

Mathematical Induction:

Suppose the following two statements are true:

1. P(a) is true.

2. For all integers k ≥ a, if P(k) is true then P(k + 1) is true.

Front 5

Principle of Mathematical Induction Let P(n) be a property that is defined for integers n, and let a be a fixed integer. Suppose the following two statements are true: 1. P(a) is true. 2. For all integers k≥a, if P(k) is true then P(k + 1) is true. Then __________________.

Back 5

Mathematical Induction:

Then the statement for all integers n ≥ a, P(n) is true.

Front 6

Principle of Mathematical Induction Let P(n) be a property that is defined for integers n, and let a be a fixed integer.

Suppose the following two statements are true:

1. P(a) is true.

2. _________________________.

Back 6

Mathematical Induction:

Suppose the following two statements are true:

1. P(a) is true.

2. For all integers k ≥ a, if P(k) is true then P(k + 1) is true.

Front 7

The validity of proof by mathematical induction is generally taken as an ______. That is why it is referred to as the principle of mathematical induction rather than as a theorem.

Back 7

axiom

Front 8

Proving a statement by mathematical induction is a two-step process. The first step is called the ______ step, and the second step is called the inductive step.

Back 8

The first step is called the basis step

Front 9

Proving a statement by mathematical induction is a two-step process. The first step is called the basis step, and the second step is called the _________ step.

Back 9

The second step is called the inductive step.

Front 10

Method of Proof by Mathematical Induction

Step 1 (basis step): Show that P(a) is true.

Step 2 (inductive step): Show that for all integers k≥a, if P(k) is true then P(k + 1) is true. To perform this step, suppose that P(k) is true, where k is any particular but arbitrarily chosen integer with k≥a. [This supposition is called the inductive ___________.] Then show that P(k + 1) is true.

Back 10

This supposition is called the inductive hypothesis.

Front 11

Method of Proof by Mathematical Induction

Step 1 (basis step): Show that P(a) is true.

Step 2 (inductive step): Show that for all integers k≥a, if P(k) is true then P(k + 1) is true. To perform this step, suppose that P(k) is true, where k is any particular but arbitrarily chosen integer with k≥a. [This supposition is called the inductive hypothesis.] Then show that _________.

Back 11

Then show that P(k + 1) is true.

Front 12

Method of Proof by Mathematical Induction

Step 1 (basis step): Show that _______

Step 2 (inductive step): Show that for all integers k≥a, if P(k) is true then P(k + 1) is true. To perform this step, suppose that P(k) is true, where k is any particular but arbitrarily chosen integer with k≥a. [This supposition is called the inductive hypothesis.] Then show that P(k + 1) is true.

Back 12

Basis step: show thatP(a) is true.

Front 13

Method of Proof by Mathematical Induction

Step 1 (basis step): Show that P(a) is true.

Step 2 (inductive step): Show that for all integers k≥a, if P(k) is true then P(k + 1) is true. To perform this step, suppose that ____________.

Then show that P(k + 1) is true.

Back 13

Suppose that P(k) is true, where k is any particular but arbitrarily chosen integer with k≥a. [This supposition is called the inductive hypothesis.]

Front 14

To construct a proof by induction, you must first identify the __________ P(n).

For example, P(n) might be the equation:

1 + 2 + ... + n = (n(n + 1))/2

Back 14

First identify the property P(n)

Front 15

In the basis step of the proof, you must show that the property is true for n = 1, or, in other words that P(1) is true.

Back 15

basis step

Front 16

In the basis step of the proof, you must show that the property is true for n = 1, or, in other words that P(1) is true.

Back 16

show that for n = 1, or p(1) is true

Front 17

In the inductive step, you assume that P(k) is true, for a particular but arbitrarily chosen integer k with k≥1. [This assumption is the inductive hypothesis.]

You must then show that P(k + 1) is true.

Back 17

inductive step

Front 18

In the inductive step, you assume that P(k) is true, for a particular but arbitrarily chosen integer k with k≥1. [This assumption is the inductive hypothesis.]

You must then show that P(k + 1) is true.

Back 18

inductive hypothesis

Front 19

In the inductive step, you assume that P(k) is true, for a particular but arbitrarily chosen integer k with k≥1. [This assumption is the inductive hypothesis.] You must then show that P(k + 1) is true.

Back 19

then show that P(k + 1) is true.

Front 20

1 + 2 + ... + (k + 1) = (1 + 2 + ... + k) + (k + 1)

The next-to-last term is k because...

Back 20

...because the terms are successive integers and the last term is k + 1.

Front 21

When using proof by mathematical induction, the first sentence of your proof isn't necessarily "suppose". Instead, state:

"Let the property P(n) be the equation: "

and then list the equation proposed in the theorem.

Back 21

Let the property P(n) be the equation:

Front 22

When using proof by mathematical induction, the first sentence of your proof isn't necessarily "suppose". Instead, state: "Let the property P(n) be the equation: " and then list the equation proposed in the theorem.

Back 22

Let the property....

Front 23

After stating " Let the property P(n) be the equation: " and stating what P(n) is, the next two steps are to:

Show that P(1) is true: [and]

Show that for all integers k ≥ 1, if _____ then ____.

Back 23

For all integers k ≥ 1

If P(k) is true then P(k + 1) is also true:

Front 24

The story is told that one of the greatest mathematicians of all time, Carl Friedrich _____ (1777–1855), was given the problem of adding the numbers from 1 to 100 by his teacher when he was a young child, and succeeded to the teacher's surprise.

Back 24

Gauss

Front 25

If a sum with a variable number of terms is shown to be equal to a formula that does not contain either an ellipsis or a summation symbol, we say that it is written in _____ form.

Back 25

closed form

Front 26

If a sum with a variable number of terms is shown to be equal to a formula that does not contain either an ________ or a _________ symbol, we say that it is written in closed form.

Back 26

does not contain either an ellipsis or a summation symbol

Front 27

In a geometric sequence, each term is obtained from the preceding one by multiplying by a constant factor. If the first term is 1 and the constant factor is r, then the sequence is 1,r,r^2 ,r^3 ,...,r^n ,.... The sum of the first n terms of this sequence is given by the formula:

Back 27

Front 28

In a geometric sequence, each term is obtained from the preceding one by ____________ by a constant factor.

Back 28

multiplying by a common factor

Am*Am+1*Am+2...

Front 29

In natural science courses, deduction and induction are presented as alternative modes of thought—deduction being to infer a conclusion from general principles using the laws of logical reasoning. In this sense, then, mathematical induction is not inductive but ________.

Back 29

Mathematical induction is deductive in a natural science sense.

Front 30

a proof by mathematical induction gets to the essence of why the __________ holds in general. It reveals the mathematical mechanism that necessitates the truth of each successive case from the previous one.

Back 30

why a pattern holds in general

Front 31

mathematical induction makes knowledge of the general _______ a matter of mathematical certainty rather than vague conjecture.

Back 31

makes knowledge of the general pattern