And 236 comes to an end...

And what an end! A term test on the last Friday, just one week prior to the course's final exam and just three days before my first exam! I think Test 3 went well for me, even though with proofs you never know if you wrote too much or too little until you get the grader's feedback.

Time flies, and this semester was no exception. I know I enjoyed CSC236 a lot, this and CSC258 were the best university courses I took so far, both had material that really grabbed my interest and both were a lot of fun to spend time on. I'd like to thank my instructor Professor Heap for teaching 236 so well - quality lectures really make the difference.

It was great to see material from this course build so seamlessly onto itself, what started as basic induction proofs turned out to evolve into methods of assessing program correctness, defining functions, and even constructing languages. The last few bits concerning finite state automata were especially interesting, I wish more of the course focused on building and experimenting with them.

Now to prepare for the coming week of fire... 4 exams in 5 days, and 1 more the Wednesday after :-)

Problem-solving: simple induction

I will solve a simple induction problem from the course notes, following the G. Polya approach.

Course Notes, Chapter 1, exercise 7
-----------------------------------
Use induction to prove that, for any integers m >= 2 and n >= 1,
Sum(0 to n)_(m^t) = (m^(n + 1) - 1) / (m - 1)

1. Understanding the problem

We need to show that the equality holds for arbitrary integers m and n, provided m and n satisfy the given conditions.

2. Devising a plan

The text requires this problem be solved by induction, and seeing how this involves a summation and the need to prove an equality for arbitrary values, the context looks fit for such a method. Simple induction it will be.

3. Carrying out the plan

P(n):  For all integers m >= 2, Sum(0 to n)_(m^t) = (m^(n+1) - 1) / (m - 1)
Claim: For all integers n >= 1, P(n)

Base Case n = 1

    Let m be an arbitray integer >= 2.

    Sum(0 to 1)_(m^t) = m^0 + m^1
                      = 1 + m
                      = m + 1
    
    (m^(1+1) - 1) / (m - 1) = (m^2 - 1) / (m - 1)
                            = (m - 1)(m + 1) / (m - 1)
                            = m + 1
                              
    So P(1) is true.
    
Induction Step

    Assume P(n) is true for some n >= 1.
    
    Let m be an arbitray integer >= 2.
    
    Sum(0 to n+1)_(m^t) = Sum(0 to n)_(m^t) + m^(n+1)
                (by IH) = (m^(n+1) - 1) / (m - 1) + m^(n+1)
                        = (m^(n+1) - 1 + m^(n+1) * (m - 1)) / (m - 1)
                        = (m^(n+1) - 1 + m^(n+2) - m^(n+1)) / (m - 1)
                        = (m^(n+2) - 1) / (m - 1)
                        = (m^((n+1)+1) - 1) / (m - 1)
                        
    This implies that P(n+1) is true, which means that P(n) -> P(n+1).
    Then for all integers n >= 1, P(n) is true.

Since m was always taken as an arbitrary integer >= 2, I conclude that
for all integers n >= 1 and m >= 2, Sum(0 to n)_(m^t) = (m^(n+1) - 1) / (m - 1).

4. Looking back

I only made induction on n, and let m be an arbitrary integer >= 2 every time. This covers all valid m and n, without having to worry about both. However, instead of letting m be arbitrary, I could have made induction on m at each step of the proof. However, it seemed like overkill when a more compact alternative was so readily available.