Woche Zwei

So it has been 2 weeks since my last slog since I started early when Heap emailed us during thanksgiving weekend saying we should start during that week. Anyways there's a lot to recap on during this course since my last slog.

 Friday's lecture we got our midterms back and I was surprised to see I did so well. I looked through the marking scheme for the midterm and our proof structures and layout of our proof was worth a lot and the tricks inside the induction step weren't worth as much. I think this attributed to my higher mark since I think my induction step was a little too long and not precise for question 2 and for question 3 as well. I examined my midterm carefully I believe the 2 marks I lost were from the conclusion statements at the end of each question. My conclusion was very brief since I basically wrote "for all n, P(n)" and this is exactly what Heap said he would be deducting a mark for. I must avoid this mistake and state a clear conclusion that shows my understanding of the structure of the proof and why the conclusion holds. Also for the induction steps I should definitely avoid writing a paragraph explaining everything like I did in question 2. At the time I was just quickly racing along writing down all my thoughts and reasoning on that paper without thinking twice about details that might not have been necessary and obvious. Then the complete opposite on question 3, I barely wrote any guts inside the induction step and it was more structure than proof (except for a terrible conclusion I believe). I think I did skip or 2 that could have added more clarity for a reader at our level, I felt the time squeeze on that question and was forced to skip some steps there. Overall I'm glad I did well and hope I can avoid these mistakes, by knowing the marking scheme and my mistakes, so on the next midterm I can get a perfect!

Before writing this slog I was also looking at tutorial #3 from last week and tried the problems since I didn't have any time to do it last week and the TA didn't have time for question 2 and 3. Doing the 3rd problem seemed the most fun because unwinding a recurrence is tricky and sometimes can be unexpected as to what the closed form is.

The question was find the closed form of G(n) = 1  if n < 2, G(n) = 1 + G(n-1) + G(n-2)   if n >= 2

So carefully unwinding the function as suggested I a series of equivalences of the same form as above for n >= 2, except with 2 coefficients in front of each G(n-i). Expanding the recurrence and collecting like terms each time allowed me to see that the coefficients in front of the initially G(n - 1) started at 1 and then went to 2G(n - 2), 3G(n - 3), 5G(n - 4), 8G(n - 5), 13G(n - 6).... and so on. Looking at just this term the pattern became obvious and surprising initially since it was a Fibonacci sequence of coefficients. The form followed exactly fib(i + 1)G(n - i) and similarly for the 2nd term which was initially G(n - 2) the form became fib(i)G(n - i -1). Now this is still not in closed form, so working through till (n - i) = 0 so that i = n, we see that G(n - n + 1) = 1 and G(n - n) = 1. This then simplifies our equivalence to 2 fib(n + 1) + 2 fib(n) - 1. The lonely constant wasn't so lonely after all since it was the result of the coefficients on both terms minus 1, fib(i + 1) + fib(i) - 1. Now remembering the closed form of the Fibonacci sequence from our notes it can be rewritten as G(n) = 2/sqrt(5)[(Φ^n+1 - (φ)^n+1) + (Φ^n - (φ)^n)] - 1. This seems like a plausible answer since initially the G(n) function looks almost similar to the recursive definition of the Fibonacci sequence except with an added - 1. Gosh who knew counting rabbits would extend all the way here! I felt like this kind of problem was something like the other tutorial problems, similar to the notes except with a little tweak or additional trick. It might be something we can expect on a midterm or exam, although it is a little tedious and a time killer!

I don't want to make this blog entry too long, I'll be writing up another one soon!