EF Activities

Skip to main content

Activities 7.4 Activities
A4 US

Below is a more detailed version of Procedure 7.1.2. Follow the steps of Procedure 7.4.1 to create a proof by induction for each of the requested proofs in this activity set.

Procedure 7.4.1. Mathematical induction, step-by-step.

🔗
Write the statement with $n$ replaced by $k .$
🔗
Write the statement with $n$ replaced by $k + 1 .$
🔗
Identify the connection between the $k^{th}$ statement and the ${(k + 1)}^{th}$ statement.
🔗
Complete the induction step by assuming that the $n = k$ version of the statement is true, and using this assumption to prove that the $n = k + 1$ version of the statement is true.
🔗
Complete the induction proof by proving the base case.

Activity 7.1.

A binary string is a “word” in which each “letter” can only be

0

or

1 .

Prove that there are

2^{n}

different binary strings of length

n .

Activity 7.2.

Prove that for every positive integer

n,

the binomial

1 - x^{n}

can be factored as

(1 - x) (1 + x + x^{2} + \dots + x^{n - 1}) .

Activity 7.3.

Prove that the following argument is valid for all positive integers

n .

(p_{1} \land q_{1}) \to r_{1}

(p_{2} \land q_{2}) \to r_{2}

⋮

(p_{n} \land q_{n}) \to r_{n}

p_{1} \land p_{2} \land \dots \land p_{n}

(q_{1} \to r_{1}) \land (q_{2} \to r_{2}) \land \dots \land (q_{n} \to r_{n})

Careful.

Recall that in this context, the words valid and true do not have the same meaning.

Activity 7.4.

Prove that a truth table involving

n

statement variables requires

2^{n}

rows.

Activity 7.5.

Prove that a knight can be moved from any square to any other square on an

n \times n

chess board by some sequence of allowed moves, for every

n \geq 4 .

<Prev ^Top Next>