SE 500 Mathematics for Software Engineering
Fall 2024
HW #9: Mathematical Induction
Due: 5pm December 6 (Friday)

1. Prove by (weak) mathematical induction that  (+i | 1≤i≤n : 2i + 4) = n2 + 5n  for all n ≥ 0.

2. Prove by (weak) mathematical induction that  (+i | 0≤i≤n : bi) = (bn+1 - 1) / (b-1)  for all n ≥ 0.

3. Define f : ℕ → ℕ as follows:

f.0 = 1
f.1 = 3
f.n =  2·f(n−1) − f(n−2)    (for n≥2)

Prove by (strong) mathematical induction that f.n = 2n+1  for all n ≥ 0.

4. Define g : ℕ → ℕ as follows:

g.0 = 1
g.1 = 5
g.n =  7·g(n−1) − 10·g(n−2)    (for n≥2)

Prove by (strong) mathematical induction that g.n = 5n  for all n ≥ 0.

5. 
       *
      / \
     /   \
    /     \
   *       *
  / \      |
 /   \     |
*     *    *
     / \
    /   \
   *     *
   |    / \
   |   /   \
   *  *     *
   |        | 
   |        |
   *        *
A rooted binary tree has one of the three forms shown below, where each of TC, TL, and TR is itself a rooted binary tree. An example appears to the right.

Root is
a leaf
T0		 Root has
one child
T1		 Root has
two children
T2		 
   *
 
    *
    |
    |
    |
    |
    *
   / \
  /   \
 / TC  \
+-------+
 
         *
        / \
       /   \
      /     \
     /       \
    *         *
   / \       / \
  /   \     /   \
 / TL  \   / TR  \
+-------+ +-------+

The height of a rooted tree is equal to the length of a longest path among all paths from the root to the leaves. Recursively, the height of a rooted tree is zero if the root is its only node and, otherwise, the height is one plus the height of its "tallest" proper subtree (which would be a subtree rooted at one of the children of the root).

Referring to the diagram above, we have

Prove by (weak) mathematical induction that, for all n≥0, every rooted binary tree having at least 2n nodes has height at least n.

To clarify, what is to be proved is that, for all n≥0 and all rooted binary trees T,

v(T) ≥ 2n   ⟹   h(T) ≥ n

where v(T) is the number of nodes/vertices in T and h(T) is the height of T.

Hint: Regarding the induction step, suppose that T is a rooted binary tree having at least 2n+1 nodes. If T is of the form of T1, how many nodes must be in TC? If T is of the form of T2, how many nodes must be in larger among TL and TR?