7.4: Activities

Below is a more detailed version of Procedure 7.1.1. Follow the steps of Procedure \(\PageIndex{1}\) to create a proof by induction for each of the requested proofs in this activity set. 

Procedure \(\PageIndex{1}\): Mathematical induction, step-by-step

1. Write the statement with \(n\) replaced by \(k\text{.}\)
2. Write the statement with \(n\) replaced by \(k+1\text{.}\)
3. Identify the connection between the \(k^{th}\) statement and the \((k+1)^{th}\) statement.
4. 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.
5. Complete the induction proof by proving the base case.

Activity \(\PageIndex{1}\)

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 \(\PageIndex{2}\)

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

Activity \(\PageIndex{3}\)

Prove that the following argument is valid for all positive integers \(n\text{.}\) 

\begin{aligned}
\left(p_{1} \wedge q_{1}\right) &\rightarrow r_{1} \\
\left(p_{2} \wedge q_{2}\right) &\rightarrow r_{2} \\
&\vdots \\
\left(p_{n} \wedge q_{n}\right) & \rightarrow r_{n} \\
p_{1} \wedge p_{2} \wedge &\cdots \wedge p_{n}\\ \hline \left(q_{1} \rightarrow r_{1}\right) &\wedge\left(q_{2} \rightarrow r_{2}\right) \wedge \cdots \wedge\left(q_{n} \rightarrow r_{n}\right)
\end{aligned}

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

Activity \(\PageIndex{4}\)

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

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