Taiwan IMO Selection Camp

(a) (2 points) Let $F_n = \sum_{S \subseteq T} f(S)$ for $n = 0, 1, 2, \dots$. Considering whether the number $n$ is "in" or "not in" the subset $S$, we obtain the following equality:
$$\begin{aligned} F_n &= \sum_{S \subseteq T - \{n\}} (n - f(S)) + F_{n-1} \\ &= n \times 2^{n-1} - F_{n-1} + F_{n-1} \\ &= n \times 2^{n-1}. \end{aligned}$$

(b) (5 points) Let $G_n = \sum_{S \subseteq T} g(S)$ for $n = 0, 1, 2, \dots$. Clearly $G_0 = 0$, $G_1 = 1$, $G_2 = 5$, $G_3 = 16$. Below assume $n \ge 3$. Consider whether the subset $S$ contains $n$ or not; when it contains $n$ and there is a second-largest element, let the second-largest element be designated as $k$, so we obtain

$$\begin{align*} G_n &= G_{n-1} + n \times 2^{n-1} - \sum_{k=1}^{n-1} G_{k-1} \\ &= G_{n-1} + n \times 2^{n-1} - G_{n-2} - \sum_{k=1}^{n-2} G_{k-1} \\ &= G_{n-1} + n \times 2^{n-1} - G_{n-3} - (n-2) \times 2^{n-3} + \sum_{k=1}^{n-3} G_{k-1} - \sum_{k=1}^{n-2} G_{k-1} \\ &= G_{n-1} - 2G_{n-3} + (3n+2) \times 2^{n-3}, \end{align*}$$
or
$$G_n - G_{n-1} + 2G_{n-3} = (3n + 2) \times 2^{n-3}.$$
The above recurrence is non-homogeneous. Suppose $\hat{G}_n = (\alpha + \beta n)2^n$ is a particular solution; substituting into the recurrence gives
$$\begin{align*} & (\alpha + \beta n)2^n - (\alpha + \beta(n-1))2^{n-1} + 2(\alpha + \beta(n-3))2^{n-3} = (3n + 2) \times 2^{n-3} \\ \Rightarrow \quad & (8\alpha - 4\alpha + 4\beta + 2\alpha - 6\beta) + (8\beta - 4\beta + 2\beta)n = 2 + 3n \\ \Rightarrow \quad & \alpha = \beta = \frac{1}{2} \\ \Rightarrow \quad & \hat{G}_n = (1 + n)2^{n-1}. \end{align*}$$
After homogenizing the recurrence: $G_n - G_{n-1} + 2G_{n-3} = 0$, whose characteristic polynomial is $x^3 - x^2 + 2$, and the roots of the polynomial are $-1, 1+i$ and $1-i$. So the general solution of the non-homogeneous recurrence will be:
$$G_n = A(-1)^n + B(1+i)^n + C(1-i)^n + (1+n)2^{n-1}.$$

Checking the boundary conditions:
$$G_0 = 0 = A + B + C + \frac{1}{2};$$
$$G_1 = 1 = -A + (1+i)B + (1-i)C + 2;$$
$$G_2 = 5 = A + 2iB - 2iC + 6.$$
From this we obtain $A = 0, B = \frac{-1+i}{4}$ and $C = \frac{-1-i}{4}$, that is
$$G_n = \frac{-1+i}{4}(1+i)^n + \frac{-1-i}{4}(1-i)^n + (n+1)2^{n-1},$$
or
$$G_n = \frac{-1}{4}((1+i)^n + (1-i)^n) + \frac{i}{4}((1+i)^n - (1-i)^n) + (n+1)2^{n-1},$$
or
$$G_n = \frac{-1}{2} \left( \binom{n}{0} - \binom{n}{2} + \binom{n}{4} - \cdots \right) \\ \qquad + \frac{-1}{2} \left( \binom{n}{1} - \binom{n}{3} + \binom{n}{5} - \cdots \right) + (n+1)2^{n-1}$$