# 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?

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.

1. is simply wrong because already $\forall k\colon k>29$ is wrong.
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$.
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]$$