# Parity of the terms of a sequence (Tomato 7)

Problem:

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.

## Chatuspathi:

• What is this topic: Induction
• What are some of the associated concepts: Strong form of induction
• Where can learn these topics: Cheenta I.S.I. & C.M.I. courseMath Olympiad Program discusses these topics in the ‘Induction’ module.
• Book Suggestions: Elementary number theory by David Burton