Strong Induction: Finding the Inductive Hypothesis 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:


*

*∀k[(n≥k>29)∧[∃i≥0,j≥0[k=8i+5j]]]

*∀k>29[∃i≥0,j≥0[k=8i+5j]]

*∀k[(n≥k>29)→[∃i≥0,j≥0[k=8i+5j]]]

*∃i≥0,j≥0[n=8i+5j]


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

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]$$
