We went over the course information stuff and then we started with the principle of simple induction. We saw a couple of examples, like the one that we had to prove that the units digit of 3^n belongs to the set {1,3,7,9}.
In my opinion the most interesting was the one with the number of subsets of odd size of a set with n elements.
Excluding zero, you can use induction to show that we have 2^(n-1) subsets of odd size. There was another clever approach to the proof that was suggested by one of our classmates. It used the 1-1 correspondence of the subsets of odd size to the subsets of even size.
Problem Set 1 is due next week so I have to start this weekend!
4 comments:
Your classmate's observation was so good that it did away with the need for induction.
The point is to notice that there is a 1-1 correspondence between the subsets of S\{x} and the odd subset of S. If you can establish that, you simply re-use the result about there being 2^n subsets of a set of size n.
Yeap, I should have mentioned that the other approach had nothing to do with induction.
Could we have used a combinatorial approach to prove this?
crom, the destroyer:
do you have a specific proof in mind? You are more than welcome to post a sketch of a proof here.
Post a Comment