9.26.2023
Question 1: Suppose we want to prove the following open proposition over the natural numbers:
$p(n)$: $8^{n} - 3^{n}$ is a multiple of $5$.
Which of the following would constitute the base case for a proof via PMI?
(3 points)
A. $p(2)=64-9=55$
B. $p(1)=5$
C. $p(0)=0$
D. $p(3)=512-27=485$
Answer
C. $p(0)=0$Question 2: For the induction hypothesis of the proof of the open proposition
$p(n)$: $8^{n} - 3^{n}$ is a multiple of $5$,
we assume $p(k)$ is true for an arbitrary natural number. It then follows that $p(k+1)=8^{k+1}-3^{k+1} = 8×8^{k} - 3×3^{k}$. Which of the following reductions of $p(k+1)$ is needed to complete the proof?
(3 points)
A. $p(k + 1) = 8 \times (5j) - 3 \times (5m)$, for some integers $j$ and $m$.
B. $p(k + 1) = 8 \times (8j) - 3 \times (3m)$, for some integers $j$ and $m$.
C. $p(k + 1) = 8^{m} \times (5j) - 3^{j} \times (5m)$, for some integers $j$ and $m$.
D. $p(k + 1) = 8 - 3 = 5$, for all $k \geq 0$.
Answer
A. $p(k + 1) = 8 \times (5j) - 3 \times (5m)$, for some integers $j$ and $m$.Question 3: Given the proof of the following open proposition over the natural numbers (using PMI)
$p(n)$: $8^{n} - 3^{n}$ is a multiple of $5$,
which of the following open propositions can also be shown to be a tautology over the natural numbers?
(3 points)
A. $q(n) = 7^{n} - 3^{n}$ is a multiple of $5$.
B. $r(n) = 6^{n} - 2^{n}$ is a multiple of $5$.
C. $s(n) = 9^{n} - 5^{n}$ is a multiple of $5$.
D. $t(n) = 9^{n} - 4^{n}$ is a multiple of $5$.