For the induction step, suppose the claim is true for all values of k less than n. That's the induction hypothesis.

Let S be a set of size n. Now we'll show that the induction hypothesis implies that the claim is true for S as well.

Write \\(S = x_1, \ldots, x_n\\).

Now let \\(T_1\\) be all the subsets of \\(S\\) that contain \\(x_n\\), and \\(T_0\\) be all the subsets that don't contain \\(x_n\\).

Together, \\(T_0\\) and \\(T_1\\) give a partition of \\(2^S\\).

So the size of \\(2^S\\) will be obtained by summing the sizes of \\(T_0\\) and \\(T_1\\).

Now, it's easy to see that \\(T_0\\) and \\(T_1\\) have the same size. That's because every subset \\(A\\) of \\(S\\) that contains \\(x_n\\) can uniquely paired with a subset \\(A'\\) of \\(S\\) that doesn't contain \\(x_n\\). To get from \\(A\\) to \\(A'\\), you just have to remove \\(x_n\\).

Since they have equal size, the size of \\(2^S\\) is double the size of \\(T_0\\).

Now let \\(S' = S - \lbrace x_n \rbrace\\) be the set obtained by removing \\(x_n\\) from \\(S\\).

As we said, \\(T_0\\) is all subsets of \\(S\\) that don't contain \\(x_n\\).

Which means that \\(T_0\\) is the same thing as the power set of \\(S'\\).

By the induction hypothesis, the size of the power set of \\(S'\\) is \\(2^{n-1}\\).

Putting this all together, we get:

\\[|S| = 2 * |T_0| = 2 * |2^{S'}| = 2 * 2^{n-1} = 2^n\\]

That completes the proof.

Let S be a set of size n. Now we'll show that the induction hypothesis implies that the claim is true for S as well.

Write \\(S = x_1, \ldots, x_n\\).

Now let \\(T_1\\) be all the subsets of \\(S\\) that contain \\(x_n\\), and \\(T_0\\) be all the subsets that don't contain \\(x_n\\).

Together, \\(T_0\\) and \\(T_1\\) give a partition of \\(2^S\\).

So the size of \\(2^S\\) will be obtained by summing the sizes of \\(T_0\\) and \\(T_1\\).

Now, it's easy to see that \\(T_0\\) and \\(T_1\\) have the same size. That's because every subset \\(A\\) of \\(S\\) that contains \\(x_n\\) can uniquely paired with a subset \\(A'\\) of \\(S\\) that doesn't contain \\(x_n\\). To get from \\(A\\) to \\(A'\\), you just have to remove \\(x_n\\).

Since they have equal size, the size of \\(2^S\\) is double the size of \\(T_0\\).

Now let \\(S' = S - \lbrace x_n \rbrace\\) be the set obtained by removing \\(x_n\\) from \\(S\\).

As we said, \\(T_0\\) is all subsets of \\(S\\) that don't contain \\(x_n\\).

Which means that \\(T_0\\) is the same thing as the power set of \\(S'\\).

By the induction hypothesis, the size of the power set of \\(S'\\) is \\(2^{n-1}\\).

Putting this all together, we get:

\\[|S| = 2 * |T_0| = 2 * |2^{S'}| = 2 * 2^{n-1} = 2^n\\]

That completes the proof.