Generating function formulation The question I am given is (I am not asking for this whole question to be solved, just posting it here as reference):
Let $S$ be the set of all non-empty subsets of $\{1,...,n\}$. Define the weight $w(B)$ of a set $B\in S$ to be the smallest element of $B$. 
Prove that $Φ_{S}(x) = \frac{x^{n+1}-2^nx}{x-2}$

I believe the first step is algebraically defining the weight function so that I can use it to start formulating the generating function. I have been working on this for hours and can't figure out how to express this algebraically, especially when I don't have S expressed algebraically. Any help in correcting my thinking or starting off this question is much appreciated!
Potentially useful notes: I have determined that $\vert S\vert=2^n$ and each element of $\{1,...,n\}$ appears in $S$ a total of $2^{n-1}$ times (which I am still trying to prove).
 A: Fix $S=\{0,1,2,\dots,n-1\}$. For a subset of $S$ to have weight $i$, it cannot contain elements from $0$ to $i-1$. Then for $a_i$, we want to compute the number of subsets of $\{i,i+1,\dots, n-1\}$ which contain $i$. 
The number of subsets of $\{i,i+1,\dots, n-1\}$ is $2^{n-i}$, and the number of subsets of $\{i,i+1,\dots, n-1\}$ not containing $i$ is $2^{n-i-1}$ (i.e. they are all the subsets of $\{i+1, i+2,\dots, n-1\}$). This gives that the number of subsets of $S$ of weight $i$ is $a_i=2^{n-i}-2^{n-i-1}$. 
Then the polynomial you want is $(2^n-2^{n-1})+(2^{n-1}-2^{n-2})x+\cdots+(2^{n-(n-1)}-2^{n-n})x^{n-1}$. To get it into the form that you have, multiply top and bottom by $x-2$ to get: $\frac{x^n-2^n}{x-2}$.
(Note: I started with the set $S=\{0,1,\dots, n-1\}$, and you used the set $\{1,2, \dots, n\}$. If you want to use the second set, just multiply the polynomial above by $x$, since the second set shifts all the weights up by $1$.)
A: Compare $n$ to $n+1$. You can either add $n+1$ to each set or not add it. There's also the extra singleton $\{n+1\}$. 
So,
$$\Phi_{n+1}=2\Phi_n+x^{n+1}=\sum_{k=0}^n2^{k}x^{n+1-k}$$$
Can you finish it from here?
