For a given positive integer k, define two sequences a_n and b_n as follows: aligned a_1 &= k, & a_2 &= k, & a_n+2 &= a_n a_n+1 (n 1) b_1 &= 1, & b_2 &= k, & b_n+2 &= b_n+1^3 + 1b_n (n 1) aligned For any positive integer n, show that a_2nb_n+3 is an integer.

**Lemma 2.** For an odd prime p such that p|k, (c_m, p) = 1 (-1 m n+1). *Proof.* Suppose there is an odd prime p such that p|(c_m, c_m+1). Then Lemma 1 implies p|k, which contradicts Lemma 2. **Lemma 4.** For an odd prime p such that p^m||c_n with m 1, p^m|(c_n+1^3 + k^3f_2n+2). *Proof.* From Lemma 3, p c_n-1. From this computation align* c_n+2 &= c_n+1^3 + k^3f_2n+2c_n = c_n-1^3 c_n+1^3 + c_n-1^3 k^3f_2n+2c_n-1^3 c_n = (c_n^3 + k^3f_n)^3 + c_n-1^3 k^3f_2n+2c_n-1^3 c_n &= c_n^9 + 3c_n^6 k^3f_2n + 3c_n^3 k^6f_2n + k^9f_2n + c_n-1^3 k^3f_2n+2c_n-1^3 c_n &= c_n^9 + 3c_n^6 k^3f_2n + 3c_n^3 k^6f_2n + k^3f_2n+2(c_n-1^3 + k^3f_2n-2)c_n-1^3 c_n 9 &= c_n^9 + 3c_n^6 k^3f_2n + 3c_n^3 k^6f_2n + k^3f_2n+2 c_n-2 c_nc_n-1^3 c_n &= 1c_n-1^3 (c_n^8 + 3c_n^5 k^3f_2n + 3c_n^2 k^6f_2n + k^3f_2n+2 c_n-2) alig…

Browse · MathNet

Korean Mathematical Olympiad Final Round

South Korea algebra

Problem

For a given positive integer

k

, define two sequences

{a_{n}}

and

{b_{n}}

as follows:

a_{1} b_{1} = k, = 1, a_{2} b_{2} = k, = k, a_{n + 2} b_{n + 2} = a_{n} a_{n + 1} (n \geq 1) = \frac{b _{n + 1}^{3} + 1}{b _{n}} (n \geq 1)

For any positive integer

n

, show that

a_{2 n} b_{n + 3}

is an integer.

Solution

Lemma 2. For an odd prime

p

such that

p ∣ k

(c_{m}, p) = 1

(

- 1 \leq m \leq n + 1

).

Proof. Suppose there is an odd prime

p

such that

p ∣ (c_{m}, c_{m + 1})

. Then Lemma 1 implies

p ∣ k

, which contradicts Lemma 2.

□

Lemma 4. For an odd prime

p

such that

p^{m} ∣∣ c_{n}

with

m \geq 1

p^{m} ∣ (c_{n + 1}^{3} + k^{3 f_{2 n + 2}})

.

Proof. From Lemma 3,

p ∤ c_{n - 1}

. From this computation

c_{n + 2} = \frac{c _{n + 1}^{3} + k ^{3 f_{2 n + 2}}}{c _{n}} = \frac{c _{n - 1}^{3} c _{n + 1}^{3} + c _{n - 1}^{3} k ^{3 f_{2 n + 2}}}{c _{n - 1}^{3} c _{n}} = \frac{( c _{n}^{3} + k ^{3 f_{n}} ) ^{3} + c _{n - 1}^{3} k ^{3 f_{2 n + 2}}}{c _{n - 1}^{3} c _{n}} = \frac{c _{n}^{9} + 3 c _{n}^{6} k ^{3 f_{2 n}} + 3 c _{n}^{3} k ^{6 f_{2 n}} + k ^{9 f_{2 n}} + c _{n - 1}^{3} k ^{3 f_{2 n + 2}}}{c _{n - 1}^{3} c _{n}} = \frac{c _{n}^{9} + 3 c _{n}^{6} k ^{3 f_{2 n}} + 3 c _{n}^{3} k ^{6 f_{2 n}} + k ^{3 f_{2 n + 2}} ( c _{n - 1}^{3} + k ^{3 f_{2 n - 2}} )}{c _{n - 1}^{3} c _{n}} = \frac{c _{n}^{9} + 3 c _{n}^{6} k ^{3 f_{2 n}} + 3 c _{n}^{3} k ^{6 f_{2 n}} + k ^{3 f_{2 n + 2}} c _{n - 2} c _{n}}{c _{n - 1}^{3} c _{n}} = \frac{1}{c _{n - 1}^{3}} (c_{n}^{8} + 3 c_{n}^{5} k^{3 f_{2 n}} + 3 c_{n}^{2} k^{6 f_{2 n}} + k^{3 f_{2 n + 2}} c_{n - 2}) (9)

the lemma follows.

□

For a positive integer

n

, if

2^{α} ∣∣ n

with a nonnegative integer

α

, we define

v (n) = α

. For a positive rational number

q = \frac{m}{n}

with integers

m

and

n

, define

v (q) = v (m) - v (n)

.

Lemma 5. If

k \equiv 0 (mod 4)

v (c_{n}) = f_{2 n}

for

n \geq 1

.

Proof. We get

v (c_{1}) = 1 = f_{2}

and

v (c_{2}) = v (c_{1}^{3} + k^{3}) - v (b_{3}) = 3 v (c_{1}) = 3 = f_{4}

. Suppose

v (c_{n}) = f_{2 n}

and

v (c_{n + 1}) = f_{2 n + 2}

. Since

v (c_{n + 1}^{3}) = 3 f_{2 n + 2} < 3 f_{2 n + 2} v (k) = v (k^{3 f_{2 n + 2}})

, Lemma 1 implies

v (c_{n + 2}) = v (c_{n + 1}^{3} + k^{3 f_{2 n + 2}}) - v (c_{n}) = 3 f_{2 n + 2} - f_{2 n} = f_{2 n + 4}

□

Lemma 6. Suppose

k \equiv 2 (mod 4)

and If

n \equiv 2 (mod 3)

, then

v (c_{n}) > f_{2 n}

. If

n \neq \equiv 2 (mod 3)

, then

v (c_{n}) = f_{2 n}

.

Proof. Since

c_{- 1} = 1

v (c_{- 1}) = 0 > f_{- 2} = - 1

. Since

c_{0} = k^{3} + 1

v (c_{0}) = 0 = f_{0}

. From

c_{1} = (k^{3} + 1)^{3} + 1 \equiv 2 (mod 8)

, we have

v (c_{1}) = 1 = f_{2}

. Since

v (c_{1}) = v (k) = 1

and

v (b_{3}) = 0

c_{2} = \frac{c _{1}^{3} + k ^{3}}{b _{3}}

implies

v (c_{2}) > 3 = f_{4}

.

Suppose

v (c_{3 m}) = f_{6 m}

and

v (c_{3 m + 1}) = f_{6 m + 2}

. Since

v (c_{3 m + 1}^{3}) = 3 f_{6 m + 2}

and

v (k^{3 f_{6 m + 2}}) = 3 f_{6 m + 2}

, we get

v (c_{3 m + 1}^{3} + k^{3 f_{6 m + 2}}) > 3 f_{6 m + 2}

. Thus

v (c_{3 m + 2}) = v (c_{3 m + 1}^{3} + k^{3 f_{6 m + 2}}) - v (c_{3 m}) > 3 f_{6 m + 2} - f_{6 m} = f_{6 m + 4}

.

Suppose

v (c_{3 m + 1}) = f_{6 m + 2}

and

v (c_{3 m + 2}) > f_{6 m + 4}

. Since

v (c_{3 m + 2}^{3}) > 3 f_{6 m + 4}

and

v (k^{3 f_{6 m + 4}}) = 3 f_{6 m + 4}

, we have

v (c_{3 m + 2}^{3} + k^{3 f_{6 m + 4}}) = 3 f_{6 m + 4}

. Therefore,

v (c_{3 m + 3}) = v (c_{3 m + 2}^{3} + k^{3 f_{6 m + 4}}) - v (c_{3 m + 1}) = 3 f_{6 m + 4} - f_{6 m + 2} = f_{6 m + 6}

.

Suppose

v (c_{3 m - 3}) = f_{6 m - 6}

v (c_{3 m - 2}) = f_{6 m - 4}

v (c_{3 m - 1}) \geq f_{6 m - 2} + 1

and

v (c_{3 m}) = f_{6 m}

. From the equation (9), we have

v (c_{3 m + 1}) = v (c_{3 m}^{3} + k^{3 f_{6 m}}) - v (c_{3 m - 1}) = v (c_{3 m - 1}^{8} + 3 c_{3 m - 1}^{5} k^{3 f_{6 m - 2}} + 3 c_{3 m - 1}^{2} k^{6 f_{6 m - 2}} + k^{3 f_{6 m}} c_{3 m - 3}) - 3 v (c_{3 m - 2}) = v (k^{3 f_{6 m}} c_{3 m - 3}) - 3 v (c_{3 m - 1}) = 3 f_{6 m} + f_{6 m - 6} - 3 f_{6 m - 4} = f_{6 m + 2} .

Thus we prove the lemma.

□

From Lemma 5 and Lemma 6, we prove that if

2^{m} ∣ c_{n}

, then

2^{m} ∣ (c_{n + 1}^{3} + k^{3 f_{2 n + 2}})

. With Lemma 4, it follows that

c_{n} ∣ (c_{n + 1}^{3} + k^{3 f_{2 n + 2}})

and

c_{n + 2}

is a positive integer.

Techniques

Recurrence relationsGreatest common divisors (gcd)Factorization techniques