Divisibility of a recursive sequence.

Let a 1 = 1 a_{1}=1 and a 2 = 3 a_{2}=3 and for n > 2 n > 2 a n = ( n + 1 ) a n 1 n a n 2 a_{n}=(n+1)a_{n-1} - na_{n-2} For how many positive integers n 1000 n \leq 1000 is a n a_{n} divisible by 11 11 ?

Details and Assumptions

Computation devices are not necessary.


The answer is 993.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Lan Nguyen Tuong
May 2, 2014

a n = ( n + 1 ) a n 1 n a n 2 a_{n} = (n+1)*a_{n-1} - n*a_{n-2} -> a n a n 1 = n ( a n 1 a n 2 ) a_{n} - a_{n-1} = n*(a_{n-1} - a_{n-2})

Set V n = a n a n 1 V_{n} = a_{n} - a_{n-1} , after that we have V n = n V n 1 = n ( n 1 ) ( n 2 ) . . . ( n ( n 3 ) ) V 2 = n ! V_{n} = n*V_{n-1} =n*(n-1)*(n-2)...(n-(n-3))*V_{2} = n! (as V 2 = 2 = 2 1 V_{2}=2=2*1 )

So a n = n ! + a n 1 = k = 1 n ( k ! ) a_{n} = n! + a_{n-1} = \sum_{k=1}^n (k!) for the first 10 terms, only a 4 , a 8 , a 10 a_{4} , a_{8}, a_{10} are divisible by 11; and we also have k = 1 10 ( k ! ) \sum_{k=1}^{10} (k!) is divisible by 11 that means for every n 11 n \geq 11 we have a n = 11 t + k = 11 n ( k ! ) a_{n} = 11*t + \sum_{k=11}^n (k!) (where 11 t = k = 1 10 ( k ! ) 11*t = \sum_{k=1}^{10} (k!) ). And since all n ! ( n 11 ) n! (n \geq 11) are divisible by 11, all a n a_{n} where n 11 n \geq 11 are divisible 11

---> We have 993 terms which are divisible by 11

1!+2!+...+n!

Nice! But how you know that 1!+2!+...+10! Is divisible by 11? Did you calculate that?

Farhan Gumay - 7 years, 1 month ago

Congrats. A nice insightful approach.

Niranjan Khanderia - 7 years, 1 month ago

Great solution! ButI couldn't understand how you know that sum of k! from k=1 to 10 is divisible by 11,,, And how do you know a4 and a8 is divisible too, Did you simply calculated 10! + 9! +8!... ?

Felipe Magalhães - 7 years, 1 month ago

same to me

Figel Ilham - 6 years, 5 months ago
Pranav Arora
May 2, 2014

a 1 1 ( m o d 11 ) a 2 3 ( m o d 11 ) a 3 4 × 3 3 × 1 9 ( m o d 11 ) a 4 5 × 9 4 × 3 33 0 ( m o d 11 ) a 5 5 × 9 45 10 ( m o d 11 ) a 6 7 × 10 4 ( m o d 11 ) a 7 8 × 4 7 × 10 38 6 ( m o d 11 ) a 8 9 × 6 8 × 4 22 0 ( m o d 11 ) a 9 9 × 6 1 ( m o d 11 ) a 10 11 × 1 0 ( m o d 11 ) a 11 11 × 1 0 ( m o d 11 ) \displaystyle \begin{array}{c}\\ a_1\equiv 1 \pmod {11}\\ a_2\equiv 3 \pmod {11}\\ a_3\equiv 4 \times 3-3\times 1 \equiv 9 \pmod {11}\\ a_4 \equiv 5\times 9-4\times 3 \equiv 33 \equiv 0 \pmod {11}\\ a_5 \equiv -5\times 9\equiv -45 \equiv 10 \pmod {11}\\ a_6 \equiv 7\times 10 \equiv 4 \pmod {11}\\ a_7 \equiv 8\times 4-7\times 10 \equiv -38 \equiv 6 \pmod {11}\\ a_8 \equiv 9\times 6-8\times 4\equiv 22 \equiv 0 \pmod {11}\\ a_9 \equiv -9 \times 6 \equiv 1 \pmod{11}\\ a_{10} \equiv 11 \times 1 \equiv 0 \pmod{11}\\ a_{11} \equiv -11\times 1\equiv 0 \pmod {11}\\ \end{array}

The subsequent terms turn out to be divisible by 11 because both a n 2 , a n 1 0 ( m o d 11 ) a_{n-2}, a_{n-1} \equiv 0\pmod {11} . Hence, the terms a 4 a_4 , a 8 a_8 and the terms from a 10 a_{10} to a 1000 a_{1000} are all divisible by 11 giving us a total of 993 \boxed{993} terms.

Note: this problem is actually from the Balkan Math Olympiad (1990 I believe).

Michael Tang - 7 years, 1 month ago

Log in to reply

No idea about that but I remember @Sreejato Bhattacharya posting a similar problem before.

Pranav Arora - 7 years, 1 month ago

Me neither..I encountered it on a book I was reading..

Thaddeus Abiy - 7 years, 1 month ago

Log in to reply

Which book?

Krishna Ar - 6 years, 11 months ago

can't understand the solution

Pritam Patra - 7 years, 1 month ago

i = 1 n i ! \displaystyle \sum_{i=1}^n i!

Akash K. - 7 years, 1 month ago

good approach ... but it's very lengthy in competition exams there is no time to solve for this much .. :(

saurabh kumar agrawal - 7 years, 1 month ago

Log in to reply

Ok....

Pranav Arora - 7 years, 1 month ago

It's very easy to do modular arithmetic quickly.

Richard Desper - 4 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...