Proving Oddness of a Recursively Defined Sequence

Prove that for the recursively defined sequence where the first term is 1, the second term is 3, and the k-th term is defined as $a_k = a_{k-2} + 2a_{k-1}$, all terms are odd.

This problem involves a recursively defined sequence, an important concept in discrete mathematics. Recursively defined sequences are those where each term is defined as a function of one or more previous terms. Solving this problem requires you to engage with the sequence's definition critically and understand the properties it enforces through its recursive nature. In this particular sequence, the task is to prove that all terms are odd.

To solve problems like this, especially involving proving all terms have a certain property, induction is a powerful tool. Induction allows you to show that the base cases hold for the property in question (here, oddness), and then demonstrate that if the property is true for some arbitrary term(s), it will also be true for the subsequent term. This technique aligns naturally with the recursive definition of sequences.

The conceptual strategy involves establishing initial cases clearly – here, the oddness of the first two terms is your base case. Then, you assume that for a certain point n, the terms up to $a_{n-1}$ are odd, and use the recursive definition to prove that $a_n$ is also odd. Thus, induction simultaneously harnesses the sequence's definition and validates the property for an infinite number of terms once the base case and inductive step are established.