MathLabs

Problem 1

Let S\mathcal S be the set of all nn-tuples (A1,A2,…,An)(A_1,A_2,\ldots,A_n) in which each AiA_i is a subset of {1,2,…,1998}\{1,2,\ldots,1998\}. For K∈SK\in\mathcal S, let f(K)=∣A1∪A2∪⋯∪An∣f(K)=|A_1\cup A_2\cup\cdots\cup A_n|. Find ∑K∈Sf(K)\sum_{K\in\mathcal S}f(K).
Step 2 of 5: Derive the recurrence
Previous stepNext step
s(n,m)=2ns(n,m−1)+(2n−1)2n(m−1)s(n,m)=2^ns(n,m-1)+(2^n-1)2^{n(m-1)}
Detailed analysis

Extend a tuple over {1,…,m−1}\{1,\ldots,m-1\} by independently choosing whether mm belongs to each AiA_i. There are 2n2^n extensions. The old union contribution is multiplied by 2n2^n; all but one extension contains mm, contributing the second term. Hence s(n,m)=2ns(n,m−1)+(2n−1)2n(m−1)s(n,m)=2^ns(n,m-1)+(2^n-1)2^{n(m-1)}.