There will be duplicates of this, so let me explain why I am asking:
I have become blind to what it may be, so I want hints. I am blind because I can do it "combinatorially".
The question wishes me to prove using induction that a n-element set has $2^n$ subsets.
Combinatorial proof
Consider the set $S=\{x_1,x_2,...,x_n\}$, we have a choice, do we include or exclude $x_i$ from our subset? This choice is independent (regardless of what we chose previously we will always have 2 options). There are $n$ decisions, so by the axiom of choice there are $2^n$ ways to choose subsets. We have now established that there are $2^n$ subsets.
There is no induction here. Surely is is a proof though?
Possible algebraic (and inductive proof)
I can show that there is a 1:1 correspondence between subsets and the string that contains Y at position i, if $x_i$ is in the subset, and N otherwise. This defines $^nC_r$ as $\frac{n!}{r!(n-r)!}$ (as a multinomial coefficient, or right from the axiom) I can then say:
$\sum^n_{i=0}^nC_i=2^n$
(Not entirely sure how to say it formally)
This is because $^nC_i$ denotes the number of ways to choose i things, so the sum from 0 to n is the number of ways to choose a subset o any length between 0 and n, which is all possible subsets, which we established was $2^n$
I'd have no idea how to prove this by induction. BUT it feels very combinatoric anyway.
Is there an inductive proof?
I did peek at some, the best example of what makes this different is:
This uses exactly the same logic as the proof of "Pascal's relation" which is certainly combinatoric. The point of this chapter is to get the reader to stop thinking of $^nC_r$ as $\frac{n!}{r!(n-r)!}$ and see it with combinatorial goggles. Unfortunately I never thought of $^nC_r$ like that (I would have seen the binomial theorem at AS level, 5 years ago, and the "axiom of choice" is trivial, I would have understood factorials 8 years ago) I also understand that there is quite a bit of overlap between some parts of Abstract Algebra and combinatorics, perhaps I am being too strict?
For $\;n=0,1,2\;$ the case is clear. Suppose it is true for $\;n\;$ , show for $\;n+1\;$ . So suppose $\;A:=\{a_1,...,a_n,a_{n+1}\}\;$ is our set, and out $\;B:=\{a_1,...,a_n\}\;$.
The gist of all this business is to observe that any subset of $\;A\;$ is either a subset of $\;B\;$ or a subset of $\;B\;$ union the singleton $\;\{a_{n+1}\}\;$ (why?!), and thus the number of subsets in $\;A\;$ is twice that of $\;B\;$ ...and from here we get by the induction hypothesis that
$$|P(A)|=2|P(B)|=2\cdot2^n=2^{n+1}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\square$$