Parity of the terms of a sequence | Tomato Problem 7

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.

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.
CAREERTEAM
support@cheenta.com