Lobov A.

Let \( n \) be a natural number. We will call a sequence \( a_1, a_2, \ldots, a_n \) interesting if for each \( i = 1, 2, \ldots, n \), one of the equalities \( a_i = i \) or \( a_i = i + 1 \) holds. We will call an interesting sequence even if the sum of its terms is even, and odd otherwise. For each odd interesting sequence, we found the product of its terms and wrote it down on the first sheet. For each even sequence, we did the same and wrote it down on the second sheet. On which sheet is the sum of the numbers greater, and by how much? (Give the answer in terms of \( n \)).
Denoting the sum containing the term $2 \cdot 3 \cdot \ldots \cdot n(n+1)$ by $A_n$, and the other by $B_n$, we will prove the equality $A_n - B_n = 1$ by induction.

Base case. $A_1 - B_1 = 2 - 1 = 1$.

Inductive step. Represent the sum $A_n$ as $A' + A''$, where $A'$ contains all terms of the form

$a_1a_2...a_{n-1}(n + 1)$, and $A''$ contains all terms of the form $a_1a_2...a_{n-1}n$. Since the sum $A'$ contains

the term $2 \cdot 3 \cdot \ldots \cdot n(n+1)$, for each of its terms $a_1a_2...a_{n-1}(n + 1)$, the sequence $a_1, a_2, ..., a_{n-1}$ has the same parity as the sequence $2, 3, \ldots, n$. Therefore, $A' = (n+1)A_{n-1}$. Correspondingly, in the sum $A''$ for each of its terms $a_1a_2...a_{n-1}n$ the parity of the sequence $a_1, a_2, ..., a_{n-1}$ is opposite to the parity of the sequence

$2, 3, \ldots, n$. Then $A'' = nB_{n-1}$, from which $A_n = A' + A'' = (n + 1)A_{n-1} + nB_{n-1}$. Similarly, $B_n = nA_{n-1} + (n + 1)B_{n-1}$. Therefore, $A_n - B_n = (n + 1)A_{n-1} + nB_{n-1} - nA_{n-1} - (n + 1)B_{n-1} = A_{n-1} - B_{n-1} = 1$.

## Answer

When $n \equiv 0,1 \pmod{4}$, the sum on the second sheet is greater by 1; for other $n$, the opposite is true. In other words, the sum that contains the term $2 \cdot 3 \cdot \ldots \cdot n(n+1)$ is greater by 1.