Try this problem from TOMATO Problem 7 based on the Parity of the terms of a sequence.
Problem: Parity of the terms of a sequence
If \( a_0 = 1 , a_1 = 1 \) and \( a_n = a_{n - 1} a_{n - 2} + 1 \) for \( n > 1 \), then:
(A) \(a_{465} \) is odd and \(a_{466} \) is even;
(B) \(a_{465} \) is odd and \(a_{466} \) is odd;
(C) \(a_{465} \) is even and \(a_{466} \) is even;
(A) \(a_{465} \) is even and \(a_{466} \) is odd;
Discussion:
First we note a pattern and then we prove that the pattern actually holds.
Note that:
\( a_0 = 1 \) is odd
\( a_1 = 1 \) is odd
\( a_2 = a_0 a_1 + 1 = 1\times 1 + 1 = 2 \) is even
\( a_3 = a_1 a_2 + 1 = 1 \times 2 + 1 = 3 \) is odd
\( a_4 = a_2 a_3 + 1 = 2 \times 3 + 1 = 7 \) is odd
\( a_5 = a_3 a_4 + 1 = 3 \times 7 + 1 = 22 \) is even
So the pattern that we observe is the following order: odd, odd, even, odd, odd, even...
We show this by strong form of induction. Suppose this pattern holds true for all n upto n = 3k+2
(that is \( a_{3k+2} = even , a_{3k+1} = odd, a_{3k}= odd \) ).
Our computations show that this is true for k =1 (so for initial value it is true).
Let us show for the next three values:
\( a_{3k+3} = a_{3k+2} \times a_{3k+1} + 1 = even \times odd + 1 = odd \)
\( a_{3k+4} = a_{3k+3} \times a_{3k+2} + 1 = odd \times even + 1 = odd \)
\( a_{3k+5} = a_{3k+4} \times a_{3k+3} + 1 = odd \times odd + 1 = even \)
Thus we showed that whenever the index is of the form 3j+2, the number is even, otherwise if the index is of the form 3j or 3j+1, the term is odd.
Since 465 and 466 are respectively of the form 3j and 3j+1, hence
\( a_{465} \) and \( a_{466} \) both are odd.
