Originally Posted by
emakarov First, since a_n refers to both a_{n-1} and a_{n-2}, the induction step must deduce P(n) from P(n-1) and P(n-2). I actually prefer to prove that P(k) and P(k+1) imply P(k+2) for k >= 2. Next, P(3) cannot be proved by the induction step because that would require P(1) and P(2), and we don't have P(1). Therefore, P(3) has to be proved as a part of the base case. After that, P(2) and P(3) would give P(4), P(3) and P(4) would give P(5) and so on.
To prove the inductive step, assume P(k) and P(k+1) are true (write these statements explicitly) and use the definition of a_{k+2} to see if a_{k+2} satisfies P(k+2).