Reversing a recurrence: a matching interpretation instead of matrix multiplication

shulk_said_no·Apr 7, 2025(edited)

The transfer matrices don't commute, so reversing their order feels dangerous. Is there a combinatorial expression for the final term that is visibly unchanged by reversing the coefficients? Problem: Let

n

be a positive integer and let

a_1, \cdots, a_{n-1}

be arbitrary real numbers. Define the sequences

u_0, \cdots, u_n

and

v_0, \cdots, v_n

inductively by

u_0 = u_1 = v_0 = v_1 = 1

, and

u_{k+1} = u_k + a_k u_{k-1}, \quad v_{k+1} = v_k + a_{n-k} v_{k-1} \text{ for } k = 1, \cdots, n-1.

Prove that

u_n = v_n

. Source: 2014 International Mathematical Olympiad Second Stage Training Camp · MNET-0G86

Open MNET-0G86 in the question bank →

4 replies

MissingNo404·Apr 8, 2025(edited)

Expand

u_n

as the sum of

\prod_{i\in S}a_i

over subsets

S\subseteq\{1,\dots,n-1\}

containing no consecutive indices, including the empty product 1.

shulk_said_no·Apr 8, 2025(edited)

For

n=4

this gives

1+a_1+a_2+a_3+a_1a_3

. That matches my expansion. Why does the recurrence select exactly those subsets?

MissingNo404·Apr 8, 2025

Split the subsets for

u_{k+1}

according to whether they contain

k

. Those not containing it contribute

u_k

; those containing it cannot contain

k-1

, and contribute

a_ku_{k-1}

no_mp_left·Apr 10, 2025

The map

i\mapsto n-i

preserves nonadjacency and reverses the coefficient list. It pairs the monomials for

u_n

with those for

v_n

. No positivity assumption is involved, since this is a polynomial identity.

Join the discussion

A hint, a different approach, or a thoughtful question can help.

Loading discussion…