0
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

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 <n$ 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.

$\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.