# Induction on a list of integers?

let $$(a_1,\cdots,a_n)$$ be a list of integers prove that if $$a_1$$ is even and $$a_n$$ is odd then there is an index $$i$$, $$1\leq i < n$$ such that $$a_i$$ is even and $$a_i+1$$ is odd. I’m extremely confused on how to even preform induction on this. What would the base case even be?

Induction on the value of $$n$$. For $$n=2$$ is trivial. If it’s true for $$n$$, take $$(a_1,\cdots,a_{n+1})$$ and choose some intermediate element $$a_k$$ with $$1 < k < n+1$$. If $$a_k$$ is odd, apply induction on $$(a_k,\cdots,a_{n+1})$$. If it’s even, apply induction on $$(a_1,\cdots,a_k)$$.
If $$a_2$$ is odd then we are done. Suppose $$a_2$$ is even. Now if $$a_3$$ is odd we are similarly done. So assume that $$a_3$$ is even. Continuing this argument $$n-2$$ times we find that for all $$1 \leq i we have $$a_i$$ is even. So in particular $$a_{n-1}$$ is even.Take $$j=n-1.$$ Then $$a_{j}$$ and $$a_{j+1}$$ have the required property.