1
$\begingroup$

A sequence is such that $a_o =1, a_1= 1, a_{n+1} =a_{n}a_{n-1}+1$ so we have to comment on divisibilty of $a_{2007} $ by 4.

I found out first few values in sequence as 1,1,2,3,7,22, .... which told me that only $a_{3n} $ is even. But can there be some other elaborative method?

$\endgroup$
2
$\begingroup$

The sequence $a_n\bmod 4$ is eventually periodic with a readily determined period ...

$\endgroup$
1
$\begingroup$

Hint $ $ There are $j<k$ with $\,(a_j,a_{j+1})\equiv (a_k,a_{k+1})\,\pmod{\!4}\ $ since there are only finitely many such pairs $\!\bmod {\!4}$. The recurrence depends only on the pair of prior values so this leads to cyclic behavior.

$\endgroup$
0
$\begingroup$

Questions regarding divisibility in general are often a lot easier to tackle using modulaic algebra since we don't care about precisely what values the numbers will assume. In case you don't know what the modulo k operator is, it is basically the remainder that you get after you divide a number by k. If a number is divisible by k, so in our case 4, then it is zero in mod 4 since there is no rest.

So in this case we can translate the first values that you got into mod 4 as follows: 1,1,2,3,3,2 ... Now let's multiply a number in mod 2 by a number in mod 3. These numbers can be written as a=(4c+2) and b=(4d+3), so the result of their multiplication is 4d+6. However, we should add an extra one in the sequence, which will give us 4d+7. As you can verify, this number is indeed 3 in mod 4. Whenever we multiply two numbers that are 3 in mod 4, the next number in the sequence will be 2.

Therefore we can conjecture that no element in the entire sequence will be divisible by 4 since each one of them will be either 2 or 3 in mod 4.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.