Real Analysis 465309.Denote the vertices of the octagon byA 1 =A, A 2 ,A 3 ,A 4 ,A 5 =E, A 6 ,A 7 ,A 8 in
successive order. Any time the frog jumps back and forth it makes two jumps, so to get
fromA 1 to any vertex with odd index, in particular toA 5 , it makes an even number of
jumps. This shows thata 2 n− 1 =0.
We compute the number of paths with 2njumps recursively. Consider the case
n>2. After two jumps, the frog ends atA 1 ,A 3 ,orA 7. It can end atA 1 viaA 2 or
A 8. Also, the configurations where it ends atA 3 orA 7 are symmetric, so they can be
treated simultaneously. If we denote byb 2 nthe number of ways of getting fromA 3 to
A 5 in 2nsteps, we obtain the recurrencea 2 n= 2 a 2 n− 2 + 2 b 2 n− 2. On the other hand, if
the frog starts atA 3 , then it can either return toA 3 in two steps (which can happen in
two different ways), or end atA 1 (here it is important thatn>2). Thus we can write
b 2 n=a 2 n− 2 + 2 b 2 n− 2. In vector form the recurrence is
(
a 2 n
b 2 n)
=
(
22
12
)(
a 2 n− 2
b 2 n− 2)
=
(
22
12
)n− 1 (
a 2
b 2)
.
To find thenth power of the matrix we diagonalize it. The characteristic equation is
λ^2 − 4 λ+ 2 =0, with rootsx= 2 +√
2 andy= 2 −√
- Thenth power of the matrix
will be of the form
X(
xn 0
0 yn)
X−^1 ,
for some matrixX. Consequently, there exist constantsα, β, determined by the initial
condition, such thata 2 n=αxn−^1 +βyn−^1. To determineαandβ, note thata 2 =0,
b 2 =1, and using the recurrence relation,a 4 =2 andb 4 =3. We obtainα=√^12 and
β=−√^12 , whencea 2 n=1
√
2
(xn−^1 −yn−^1 ), forn≥ 1.(21st International Mathematical Olympiad, 1979, proposed by Germany)
310.We first try a function of the formf (n)=n+a. The relation from the statement
yieldsa=667, and hencef (n)=n+667 is a solution. Let us show that this is the
only solution.
Fix some positive integernand definea 0 = n, andak =f(f(···(f (n)···)),
where the composition is takenktimes,k ≥ 1. The sequence(ak)k≥ 0 satisfies the
inhomogeneous linear recurrence relationak+ 3 − 3 ak+ 2 + 6 ak+ 1 − 4 ak= 2001.A particular solution isak= 667 k. The characteristic equation of the homogeneous
recurrenceak+ 3 − 3 ak+ 2 + 6 ak+ 1 − 4 ak=0is