Cheenta
How 9 Cheenta students ranked in top 100 in ISI and CMI Entrances?
Learn More

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

Knowledge Partner

Cheenta is a knowledge partner of Aditya Birla Education Academy
Cheenta

Cheenta Academy

Aditya Birla Education Academy

Aditya Birla Education Academy

Cheenta. Passion for Mathematics

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