For the first problem, is the number of subsets of size n, while is the number of all subsets.
For the second problem, see equation (8) on this Wikipedia page for an algebraic proof. A little further, it also has a combinatorial proof.
Alright, so here's the first problem.
Prove that for all positive integers n, .
This is what I have so far;
For n=1,
Assume this is true for some . Now, for n+1,
That last part is where it is hazy.
Other problem I was having trouble with is,
Show for positive integers n,
.
I have a lot of crazy things for this so far. I think this, " " is the beginning of the way to take it, but I'm not sure.
Any help or new direction is greatly appreciated. Thanks a bunch in advance!
For the first problem, is the number of subsets of size n, while is the number of all subsets.
For the second problem, see equation (8) on this Wikipedia page for an algebraic proof. A little further, it also has a combinatorial proof.
Many facts have both algebraic and combinatorial proofs. The latter are perfectly rigorous and legitimate. After all, the binomial coefficients are usually defined as the number of subsets, not through factorials. Sometimes, though, instructors explicitly require one type of proof or the other. Unless it is explicitly stated, I believe both types are legitimate (and I think that combinatorial proofs are often more elegant).Do you think they require a formal proof in a combinatorics class?
You almost finished the algebraic proof.
Just note that