Skip to main content

Print preview

Paper size
Additional printing options
Print headers
Print footers

Activities 7.4 Activities

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.

Activity 7.4.2.

A binary string is a “word” in which each “letter” can only be \(0 \) or \(1 \text{.}\)
Prove that there are \(2^n \) different binary strings of length \(n \text{.}\)

Activity 7.4.3.

Prove that for every positive integer \(n \text{,}\) the binomial \(1 - x^n \) can be factored as
\begin{equation*} 1 - x^n = (1 - x) (1 + x + x^2 + \dotsb + x^{n-1}) \text{.} \end{equation*}

Activity 7.4.4.

Prove that for every positive integer \(n \text{,}\) the following argument is valid.
\((p_1 \lgcand q_1) \lgccond r_1 \)
\((p_2 \lgcand q_2) \lgccond r_2 \)
\(\phantom{(p_2 \lgcand q_2)} \vdots \)
\((p_n \lgcand q_n) \lgccond r_n \)
\(p_1 \lgcand p_2 \lgcand \dotsb \lgcand p_n \)
\((q_1 \lgccond r_1) \lgcand (q_2 \lgccond r_2) \lgcand \dotsb \lgcand (q_n \lgccond r_n) \)
Careful. Recall that in this context, the words valid and true do not have the same meaning.

Activity 7.4.5.

Prove that a truth table involving \(n \) statement variables requires \(2^n \) rows.

Activity 7.4.6.

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 \ge 4 \text{.}\)
PrevTopNext