Post-a1 woes

a1 was tough for me, while I thought had a pretty good grasp of mathematical and complete induction, it appears I was wrong. A problem I had in 165 was similar, where I would understand the proof technique, but not understand what the thing I was trying to prove was. Having received a low a mark in 165, the experience in a1 was not unusual for me, but not encouraging. I hope being more on top of my work in other courses and having time to review will help with a2 and the term test coming up.

I think I've done well on both quizzes so far, so I'm not TOTALLY lost. :)

The binary tree problems were a bit confusing to me at first (mostly the terminology to be honest), but with a bit of reading I figured it out. Problem 12 in the course "textbook" was help.

The problem to prove was: For each non-empty full binary tree, the number of leaves exceeds the number of internal nodes by exactly one. To me, it sounds like an easy problem for CI, as per usual.

So, when I drew the trees to prove it to myself, it turned out true of course. To make that mouthful easier to write, I can denote it like this:

"n ÎN, n > 0, " T(n)  Þ T(L) = T(I) + 1, where T(n) is a full binary tree with n nodes, and T(L) is the leaves of that tree, and T(I) is the internal nodes.

Proving this by Complete Induction means I'll need to prove this for the n case, so P(n) = T(L) = T(L) + 1, using the n - 1 case, P(n - 1):

Base Case: n = 1. If the tree only has one node, then it is a leaf node, leaving 0 internal nodes, and 0 + 1 = 1, so P(n) is true.

Induction Step:

Assume n ÎN, n > 1, " T(n), 0 < i < n Þ T(L) = T(I) + 1.

     Then the root must be an internal node, and it must have two children, which are also roots of their own trees.

          Let the children be TL and TR, with UL and UR nodes. So n = UL + UR + 1.

          Since each tree is non empty, TL and TR have at least one node, so UL, UR > 0.

          Then we can observe two cases:

                  Case 1:  TL and TR are internal nodes, and must have two children each.
                        Then we can observe that since each internal node has must have 2 children,
                        since they are full binary trees in their own right, there is a 2 : 1 leaf to
                        to internal node ratio for each "inner tree" we are looking at. Including the
                        root an an internal node, we get a 4 : 3 ratio, proving the claim true.
                  Case 2: TL and TR are leaf nodes, and have no children.
                        Then we can observe that there are two leaves to the one root, making the
                        claim true.
           Then in both cases, P(n) is true.
      Then n = UL + UR + 1.
"n ÎN, n > 0, " T(n), 0 < i < n Þ T(L) = T(I) + 1.

In this proof, I'm pretty sure I made some errors in logic, and notation. There is also probably a much cleaner way to write this up. I'm trying to make up for it with more words to explain my mess. Hopefully even this error-ridden practice will help me on the midterm closing in! Good luck everyone!

Happy Thanksgiving!