Induction and recursion

I feel like a song and dance is in order right now, because I just solved question 3 of Assignment 1. I'm sure I will look back on this thought at the end of the semester, and think that throwing a celebration just for solving something as easy as question 3 is ridiculous. But, give me a break; I've only been working with induction for two weeks!

Question 3:

A set of 3 elements has exactly one subset of size 3 (we'll call it a 3-subset), namely itself. Find a formula for the number of 3-subsets that a set of n+3 elements has, then use Mathematical Induction to prove that your formula works for any natural number n.

I had found the formula early on by utilizing some examples and factorials. However, I was stumped on how to get from P(n) to P(n+1). I knew the question was about sets. However, the existence of an algebraic formula was so salient, that it led me to believe that the proof must be algebraically-based! Consequently, I spent an inordinate amount of time trying various algebraic methods that would let me prove P(n) => P(n+1), to no avail.

On Monday, I went to see Prof. Heap, partially because I had been trying to solve a simple induction question that was on the lecture slides but had not been covered during a lecture. (I did not ask about question 3, because I needed to figure it out myself!) The example problem asked, "How many odd-sized subsets of a set of size n are there?" I had tried using permutations and summation, but none of my solutions were perfectly correct.

When Prof. Heap showed me how there was two "types" of odd-sized subsets for a set with n elements -- those that have the nth element and those that don't -- and how the odd-sized subsets without the nth element can be derived by using the IH, it was eye-opening. The simplicity was beautiful. I was slightly surprised by how this idea did not even briefly occur to me. The recursivity of the solution is something that I should be familiar with, thanks to CSC148. I guess I was rather distracted by my zeal to find an algebraic solution instead.

When I returned to work on question 3 of A1 earlier, it hit me how similar the simple induction question on the slides and question 3 were. All I needed to do was to divide and conquer the 3-subsets! Following that realization, everything just fell into place.

Now, to tackle question 4...

Today: Warsaw, Poland
In the spirit of recursion, today we're in Warsaw, Poland to look at some famous recursive fractals by mathematician Wacław Sierpiński (1882-1969). The Sierpinski triangle is rather entertaining to doodle in your page margins when you're bored in lectures.

This will be posted after Assignment 1 is due, in case there are strong hints about question 3 that I should not be publicly stating.