Let n be a positive integer and let a_1, , a_n-1 be arbitrary real numbers. Define the sequences u_0, , u_n and v_0, , v_n inductively by u_0=u_1=v_0=1, and u_k+1=u_k+a_k u_k-1, v_k+1=v_k+a_n-k v_k-1 for k=1, , n-1 . Prove that u_n=v_n.

Browse · MathNet

International Mathematical Olympiad Shortlisted Problems

algebra

Problem

Let

n

be a positive integer and let

a_{1}, \dots, a_{n - 1}

be arbitrary real numbers. Define the sequences

u_{0}, \dots, u_{n}

and

v_{0}, \dots, v_{n}

inductively by

u_{0} = u_{1} = v_{0} = 1

, and

u_{k + 1} = u_{k} + a_{k} u_{k - 1}, v_{k + 1} = v_{k} + a_{n - k} v_{k - 1} for k = 1, \dots, n - 1.

Prove that

u_{n} = v_{n}

Solution

We prove by induction on

k

that

u_{k} = 0 < i_{1} < \dots < i_{t} < k i_{j + 1} - i_{j} ⩾ 2 \sum a_{i_{1}} \dots a_{i_{t}} (1)

Note that we have one trivial summand equal to 1 (which corresponds to

t = 0

and the empty sequence, whose product is 1). For

k = 0, 1

the sum on the right-hand side only contains the empty product, so (1) holds due to

u_{0} = u_{1} = 1

. For

k ⩾ 1

, assuming the result is true for

0, 1, \dots, k

, we have

u_{k + 1} = 0 < i_{1} < \dots < i_{t} < k, i_{j + 1} - i_{j} ⩾ 2 \sum a_{i_{1}} \dots a_{i_{t}} + 0 < i_{1} < \dots < i_{t} < k - 1, i_{j + 1} - i_{j} ⩾ 2 \sum a_{i_{1}} \dots a_{i_{t}} \cdot a_{k} = 0 < i_{1} < \dots < i_{t} < k + 1, i_{j + 1} - i_{j} ⩾ 2, k \in / {i_{1}, \dots, i_{t}} \sum a_{i_{1}} \dots a_{i_{t}} + 0 < i_{1} < \dots < i_{t} < k + 1, i_{j + 1} - i_{j} ⩾ 2, k \in {i_{1}, \dots, i_{t}} \sum a_{i_{1}} \dots a_{i_{t}} = 0 < i_{1} < \dots < i_{t} < k + 1, i_{j + 1} - i_{j} ⩾ 2 \sum a_{i_{1}} \dots a_{i_{t}},

as required. Applying (1) to the sequence

b_{1}, \dots, b_{n}

given by

b_{k} = a_{n - k}

for

1 ⩽ k ⩽ n

, we get

v_{k} = 0 < i_{1} < \dots < i_{t} < k i_{j + 1} - i_{j} ⩾ 2 \sum b_{i_{1}} \dots b_{i_{t}} = n > i_{1} > \dots > i_{t} > n - k i_{j} - i_{j + 1} ⩾ 2 \sum a_{i_{1}} \dots a_{i_{t}} (2)

For

k = n

the expressions (1) and (2) coincide, so indeed

u_{n} = v_{n}

.

Solution 2: Define recursively a sequence of multivariate polynomials by

P_{0} = P_{1} = 1, P_{k + 1} (x_{1}, \dots, x_{k}) = P_{k} (x_{1}, \dots, x_{k - 1}) + x_{k} P_{k - 1} (x_{1}, \dots, x_{k - 2}),

P_{n}

is a polynomial in

n - 1

variables for each

n ⩾ 1

. Two easy inductive arguments show that

u_{n} = P_{n} (a_{1}, \dots, a_{n - 1}), v_{n} = P_{n} (a_{n - 1}, \dots, a_{1})

so we need to prove

P_{n} (x_{1}, \dots, x_{n - 1}) = P_{n} (x_{n - 1}, \dots, x_{1})

for every positive integer

n

. The cases

n = 1, 2

are trivial, and the cases

n = 3, 4

follow from

P_{3} (x, y) = 1 + x + y

and

P_{4} (x, y, z) = 1 + x + y + z + x z

. Now we proceed by induction, assuming that

n ⩾ 5

and the claim hold for all smaller cases. Using

F (a, b)

as an abbreviation for

P_{∣ a - b ∣ + 1} (x_{a}, \dots, x_{b})

(where the indices

a, \dots, b

can be either in increasing or decreasing order),

F (n, 1) = F (n, 2) + x_{1} F (n, 3) = F (2, n) + x_{1} F (3, n) = (F (2, n - 1) + x_{n} F (2, n - 2)) + x_{1} (F (3, n - 1) + x_{n} F (3, n - 2)) = (F (n - 1, 2) + x_{1} F (n - 1, 3)) + x_{n} (F (n - 2, 2) + x_{1} F (n - 2, 3)) = F (n - 1, 1) + x_{n} F (n - 2, 1) = F (1, n - 1) + x_{n} F (1, n - 2) = F (1, n)

as we wished to show.

Solution 3: Using matrix notation, we can rewrite the recurrence relation as

(u _{k + 1} - u _{k} u _{k + 1}) = (a _{k} u _{k - 1} u _{k} + a _{k} u _{k - 1}) = (1 + a_{k} a_{k} - a_{k} - a_{k}) (u _{k} - u _{k - 1} u _{k})

for

1 ⩽ k ⩽ n - 1

, and similarly

(v_{k + 1}; v_{k} - v_{k + 1}) = (v_{k} + a_{n - k} v_{k - 1}; - a_{n - k} v_{k - 1}) = (v_{k}; v_{k - 1} - v_{k}) (1 + a_{n - k} a_{n - k} - a_{n - k} - a_{n - k})

for

1 ⩽ k ⩽ n - 1

. Hence, introducing the

2 \times 2

matrices

A_{k}=\left(\right)

we have

(u _{k + 1} - u _{k} u _{k + 1}) = A_{k} (u _{k} - u _{k - 1} u _{k}) and (v_{k + 1}; v_{k} - v_{k + 1}) = (v_{k}; v_{k - 1} - v_{k}) A_{n - k} .

for

1 ⩽ k ⩽ n - 1

. Since

(u _{1} - u _{0} u _{1}) = (0 1)

and

(v_{1}; v_{0} - v_{1}) = (1; 0)

, we get

(u _{n} - u _{n - 1} u _{n}) = A_{n - 1} A_{n - 2} \dots A_{1} \cdot (0 1) and (v_{n}; v_{n - 1} - v_{n}) = (1; 0) \cdot A_{n - 1} A_{n - 2} \dots A_{1} .

It follows that

(u_{n}) = (1; 0) (u _{n} - u _{n - 1} u _{n}) = (1; 0) \cdot A_{n - 1} A_{n - 2} \dots A_{1} \cdot (0 1) = (v_{n}; v_{n - 1} - v_{n}) (0 1) = (v_{n}) .

Techniques

Recurrence relationsPolynomial operationsMatricesRecursion, bijection