Proof by strong induction for odd and even sequence

Question

I have a proof by strong induction question (I won't ask the full question since someone in a previous course got in trouble for it). We basically have to prove, for a recurring sequence, that when $n$ is an odd the result of $S(n)$ is odd and when $n$ is an even number $S(n)$ is even.

I know that for strong induction we have to show multiple basis cases but with the induction step I am not sure in this case whether we have to to do it in two parts one showing that it's odd and one showing that it's even. Could anyone point me to the right direction?

Answer 1

After you have split into cases for $n$ even or $n$ odd, you tell us that you must prove something about $S(n)$ using strong induction? Without knowing the question it is hard to tell.

Perhaps you might need to induct on even and odd terms separately.

For example, if we have some recurrence relationship between $a_{n}$ and $a_{n+2}$ for some sequence $S$ then we might use induction to get information about $a_{n+4}$ and in the case of strong induction to get information about $a_{n+2}$ from $\{a_{2},a_{4},...,a_{n}\}$.

Does this help at all?