Topic - Proof by Induction (Algorithm Analysis)

Please show all work for my understanding. Thanks!

Problem \#1: Binary Trees The depth of a node in a tree is the length of the path from that node to the root node. (The depth of the node in a tree having a single node is zero.) In a full, balanced binary tree, every node has either no children or two children, and every leaf node has the same depth. Prove by induction that in a full balanced binary tree of depth n, the total number of nodes is 2n+11. (Five points.) Problem \#2: Points and Line Segments Suppose I draw n points, and I connect every point to every other point with a line segment. How many line segments will there be? Prove this inductively