1
$\begingroup$

Consider this claim:

Every positive integer greater than 29 can be written as a sum of a non-negative multiple of 8 and a non-negative multiple of 5.

Assume you are in the inductive step and trying to prove P(n+1) using strong induction. What would be the inductive hypothesis for this problem, if formalized and written in logical notation?

Answer Choices:

  1. ∀k[(n≥k>29)∧[∃i≥0,j≥0[k=8i+5j]]]
  2. ∀k>29[∃i≥0,j≥0[k=8i+5j]]
  3. ∀k[(n≥k>29)→[∃i≥0,j≥0[k=8i+5j]]]
  4. ∃i≥0,j≥0[n=8i+5j]

Please provide an explanation, I'm really trying to learn this stuff.

$\endgroup$
1
$\begingroup$
  1. is simply wrong because already $\forall k\colon k>29$ is wrong.

  2. is the theorem you want to prove.

  3. is the hypothesis you may use in order to prove $P(n+1)$ (under the additional condition that $n+1>29$), i.e. this is the strong inductive hypothesis that $P(k)$ holds for all $k$ with $29<k\le n$.

  4. is the property $P(n)$ you want to prove about $n$ for all $n>29$.

$\endgroup$
1
$\begingroup$

3) is the right one. In general strong induction means in fact you do not have $P(n)$ as hypothese. But 'more strongly' that $\forall k\leq n\; P\left(k\right)$ is your hypothese. Notice that $P\left(n\right)$ is a consequence of this hypothese. Here $P(n)$ is the statement: $$n>29\Rightarrow\exists i\geq0\exists j\geq0\left[n=8i+5j\right]$$

Personally in your case I would write $\forall k\leq n\; P\left(k\right)$ as: $$\forall k\leq n\left[k>29\Rightarrow\exists i\geq0\exists j\geq 0\left[k=8i+5j\right]\right]$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.