1990 AMC 12 Problem 30

Question

If

R_n=\frac12(a^n+b^n),

where

a=3+2\sqrt2,

b=3-2\sqrt2,

and

n=0,

1,

2,

\ldots,

then

R_{12345}

is an integer. Its units digit is

1

3

5

7

9

Use

a+b=6

and

ab=1

to obtain a recurrence for

R_n

Compute the recurrence modulo

10

and look for a short period

Because

a,b

are roots of

t^2-6t+1=0,

R_n=6R_{n-1}-R_{n-2}.

Starting with

R_0=1,\ R_1=3,

the units digits are

1,3,7,9,7,3,1,\ldots,

with period

6.

Since

12345\equiv3\pmod6,

the units digit is the same as that of

R_3,

namely

9.

Thus the correct answer is E.

Problem 30 in other years