week.five

reminder: test on friday!

on monday, we proved DIY in closed forms, H(n). in the case where n > 1, we find the quadratic equation first, then the roots. by doing so, we came up with h_0 = 1 and h_1 = 2 (derived from h^2 = 3h - 2). plugging in these values into H(n): (note: hi_j = h superscript i, subscript j)
H(0) = 0 = \alpha.h0_0 +\beta.h0_1 => \alpha = -\beta (*)
H(1) = 2 =\alpha.h1_0 + \beta.h1_1 => \alpha + 2.\beta = \alpha - 2.\alpha = -\alpha (by (*))
from this we determined \alpha = -2 and \beta = 2 (this was checked into H(n), and proven true). next, we proved that if two tree, T_1 and T_2, are disjoints (i.e.: share no node(s) in common), then a new tree can be formed by placing new root, r, on top of the two trees - denoted: (r, T_1, T_2). My thought on this was "oh, no...trees...this makes me wanna be not environmentally-friendly".

on wednesday, we started a sort of corollary flavour of induction - structural induction. in this kind of proof, we are trying to proof if a certain structure, say tree T, can be defined as a predicate of a statement. in class, we proved the claim: (note: T_b = binary tree)
\forall T \in T_b, |nodes(T)| <= 2^(h(T) + 1) - 1 = P(T)
for the empty tree, \lambda, P(\lambda) was shown to be true. through algebra and some known facts, we were able to carry out the induction step to prove that P(T) holds for all T. we also structurally induced the claim about the case of "matched parentheses": (note: MP = matched parentheses, s = string, L(s)/R(s) = number of left/right parentheses)
\forall s \in NP, every initial segment s' of s has L(s) >= R(s).
i personally had a really hard time figuring out and making out of the proof itself - mainly because it was unclear whether a parenthesis is a substring of some string.

on friday, we did the term test #1. i was 25 minutes late =|. but i think i managed to get some decent grades. let's just see what happens...