Track / Stage 5 / 312 of 400 #1392 of 2444

Problem 1392

AIME late

Combinatorics Difficulty 5.7 Prove it South-Afrika · South Africa · 2011

Consider all the subsets of $\{1, 2, \ldots, N\}$ that do not contain two consecutive numbers. For each subset, calculate the product of the members of the set. What is the sum of the squares of these products?

Note: the product of the elements of an empty set is one.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Let $P(N)$ be the sum of squares of the product of these subsets. For $N = 0$ there is only the empty subset, so $P(0) = 1$ . For $N = 1$ , we add the subset $\{1\}$ , so $P(1) = 2$ . For $N = 2$ , we add an extra set $\{2\}$ , so $P(2) = 6$ . Evaluating $P(3) = 24$ , one can guess that $P(N) = (N+1)!$ . We show this by induction:

To find $P(N + 1)$ , we have all the sets without element $N + 1$ , which has sum $P(N)$ , and those with $N + 1$ , which cannot contain $N$ . The product of each of those sets increases by $N + 1$ , so the recurrence is $P(N+1) = P(N) + N^2P(N-1)$ . The claim holds for small $N$ . Suppose it works for some integer $n$ . Then
$P(n + 1) = P(n) + (n + 1)^2 P(n - 1) = (n + 1)! + (n + 1)^2 n! = (n + 2)!,$
so the induction holds, and $P(N) = (N + 1)!$ for all integers $N$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.