Recurrences seem lovely!

A sequence starts with a 0 = 0 a_0=0 and the next term is a 1 = 1 a_1=1 .

If the further terms are given by

a n = 7 a n 1 10 a n 2 + 7 \displaystyle a_n= 7a_{n-1}- 10a_{n-2} + 7

Then find the last 3 digits of a 20 a_{20} .

Details :- If you don't know how to get the solutions for recurrence relations, you may try to learn it here .

This note will prove helpful in the coming problems of this series.

First Problem is bit easier than this one.


The answer is 372.

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.

1 solution

Chew-Seong Cheong
Apr 27, 2015

Thanks to Danesh Chavan for his solution to the first problem of this series. Else, I would not be able to provide a solution here.

We have to change the form of the recurrent relation as follows:

a n = 7 a n 1 10 a n 2 + 7 a n + b = a n = 7 ( a n 1 + b ) 10 ( a n 2 + b ) a n = a n = 7 ( a n 1 + b ) 10 ( a n 2 + b ) b 7 b 10 b b = 7 b = 7 4 a_n = 7a_{n-1}-10a_{n-2} + 7 \\ \Rightarrow a_n + b = a_n = 7(a_{n-1}+b)-10(a_{n-2} +b) \\ \Rightarrow a_n = a_n = 7(a_{n-1}+b)-10(a_{n-2} +b) - b \\ \Rightarrow 7b-10b -b = 7 \quad \Rightarrow b = - \frac{7}{4}

Therefore, a n 7 4 = 7 ( a n 1 7 4 ) 10 ( a n 2 7 4 ) a_n - \frac{7}{4} = 7\left( a_{n-1} - \frac{7}{4} \right) - 10\left( a_{n-2} - \frac{7}{4} \right) and the characteristic polynomial is x 2 = 7 x 10 x 2 7 x + 10 = 0 ( x 2 ) ( x 5 ) = 0 x^2 = 7x - 10 \quad \Rightarrow x^2-7x+10 = 0\quad \Rightarrow (x-2)(x-5)=0

Then we have a n a_n is of the following form:

a n 7 4 = c 1 ( 2 n ) + c 2 ( 5 n ) { a 0 7 4 = 0 7 4 = c 1 + c 2 2 c 1 + 2 c 2 = 14 4 . . . ( 1 ) a 1 7 4 = 1 7 4 = 2 c 1 + 5 c 2 2 c 1 + 5 c 2 = 3 4 . . . ( 2 ) E q . 2 E q . 1 : 3 c 2 = 11 4 c 2 = 11 12 c 1 = 8 3 a_{n} - \frac{7}{4} = c_1(2^n) + c_2(5^n) \\ \Rightarrow \begin{cases} a_{0} - \frac{7}{4} = 0 - \frac{7}{4} = c_1 + c_2 & \Rightarrow 2c_1+2c_2 = -\frac{14}{4} &...(1) \\ a_{1} - \frac{7}{4} = 1 - \frac{7}{4} = 2c_1 + 5c_2 & \Rightarrow 2c_1 + 5c_2 = - \frac{3}{4} & ...(2) \end{cases} \\ Eq.2-Eq.1: \space 3c_2 = \frac {11}{4} \quad \Rightarrow c_2 = \frac{11}{12} \quad \Rightarrow c_1 = - \frac{8}{3}

Therefore, we have a n = 11 12 ( 5 n ) 8 3 ( 2 n ) + 7 4 a_n = \frac{11}{12}(5^n) - \frac{8}{3}(2^n)+ \frac{7}{4}

a 20 = 11 12 ( 5 20 ) 8 3 ( 2 20 ) + 7 4 = 87420142874 372 \Rightarrow a_{20} = \frac{11}{12}(5^{20}) - \frac{8}{3}(2^{20})+ \frac{7}{4} = 87420142874\boxed{372}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...