An Interesting Property of $\mathbb{N}$

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function defined by

$f(k) = \sum_{C \in \mathcal{P}(S_{k})} \frac{1}{p(C)}$

Let's start by looking at the values of $f(k)$ for the first few values of $k$

$\begin{aligned} S_{1} = \{1\} & \Rightarrow f(1) = \underbrace{\frac{1}{1}}_{C = \emptyset} + \underbrace{\frac{1}{1}}_{C = \{1\}} = 2 \\ S_{2} = \{1,2\} & \Rightarrow f(2) = \underbrace{\frac{1}{1}}_{C = \emptyset} + \underbrace{\frac{1}{1}}_{C = \{1\}} + \underbrace{\frac{1}{2}}_{C = \{2\}} + \underbrace{\frac{1}{2}}_{C = \{1,2\}} = 3 \\ S_{3} = \{1,2,3\} & \Rightarrow f(3) = \underbrace{\frac{1}{1}}_{C = \emptyset} + \underbrace{\frac{1}{1}}_{C = \{1\}} + \underbrace{\frac{1}{2}}_{C = \{2\}} + \underbrace{\frac{1}{2}}_{C = \{1,2\}} + \underbrace{\frac{1}{3}}_{C = \{3\}} + \underbrace{\frac{1}{3}}_{C = \{1,3\}} + \underbrace{\frac{1}{6}}_{C = \{2,3\}} + \underbrace{\frac{1}{6}}_{C = \{1,2,3\}} = 4 \end{aligned}$

From this, it appears that $f(k) = k+1$ for these first few values of $k$ , so let's generalize this

---

Claim:

$f(k) = k+1$ for all $k \in \mathbb{N}$

Proof:

To show this, lets look at how to construct $\mathcal{P}(S_{k})$ from $\mathcal{P}(S_{k-1})$ .

We know that every set in $\mathcal{P(S_{k-1})}$ will also be in $\mathcal{P(S_{k})}$ , since $C \in \mathcal{P(S_{k-1})} \Rightarrow C \subseteq S_{k-1} \subset S_{k} \Rightarrow C \subset S_{k} \Rightarrow C \in \mathcal{P(S_{k})}$ , Hence we can express the function $f(k)$ as

$f(k) = \sum_{C \in \mathcal{P}(S_{k})} \frac{1}{p(C)} = \sum_{C \in \mathcal{P}(S_{k-1})} \frac{1}{p(C)} + \sum_{C \in \mathcal{P}(S_{k}) \ \land \ C \notin \mathcal{P}(S_{k-1})} \frac{1}{p(C)} = f(k-1) + \sum_{C \in \mathcal{P}(S_{k}) \backslash \mathcal{P}(S_{k-1})} \frac{1}{p(C)}$

It isn't too difficult to see that $C \in \mathcal{P}(S_{k}) \backslash \mathcal{P}(S_{k-1})$ only if $k \in C$ , since if $k \notin C$ , we have that $C \subset S_{k} \Rightarrow C \subset S_{k-1} \cup \{k\} \Rightarrow C \subseteq S_{k-1} \Rightarrow C \in \mathcal{P}(S_{k-1})$ , and so if $k \notin C$ and $C \subset S_{k}$ , we must have that $C \notin \mathcal{P}(S_{k}) \backslash \mathcal{P}(S_{k-1})$ .

This means that the remaining sum is over all subsets of $S_{k}$ which contain $k$ . But these sets are just all of the sets of the form $C = D \cup \{k\} : D \in \mathcal{P}(S_{k-1})$ Hence, the remaining sum becomes

$\sum_{C \in \mathcal{P}(S_{k}) \backslash \mathcal{P}(S_{k-1})} \frac{1}{p(C)} = \sum_{D \in \mathcal{P}(S_{k-1})} \frac{1}{p(D \cup \{k\})} = \sum_{D \in \mathcal{P}(S_{k-1})} \left[ \frac{1}{p(D)} \times \frac{1}{k} \right] = \frac{1}{k} \left[ \sum_{D \in \mathcal{P}(S_{k-1})} \frac{1}{p(D)} \right] = \frac{1}{k}f(k-1)$

And so, we can complete our expression for $f(k)$ as a recursive formula in terms of $f(k-1)$ as

$f(k) = f(k-1) + \sum_{C \in \mathcal{P}(S_{k}) \backslash \mathcal{P}(S_{k-1})} \frac{1}{p(C)} = f(k-1)+\frac{1}{k}f(k-1) = \frac{k+1}{k}f(k-1)$

Proceed by induction:

• $f(n) = n+1$ is true for $n=1$ , as we saw from testing the first few $k$ .

• Assume $f(j) = j+1$ for some $j \in \mathbb{N}$ . Then $f(j+1) = \frac{(j+1)+1}{j+1}f(j) = \frac{(j+2)(j+1)}{j+1} = j+2$ . This is our assumed expression for $j+1$ , which proves the inductive step.

And so we conclude that $f(n) = n+1$ for all $n \in \mathbb{N}$ . This means that $f(2017) = 2018$ , and that $\boxed{2017}$ is our answer.