SE 500 Mathematics for Software Engineering
Fall 2025
HW #9: Mathematical Induction
Due: 5pm, Friday November 14

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

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

3. Define f : ℕ → ℕ as follows:

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

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

4. In a rooted binary tree, each node has either two, one, or zero children. A node with zero children is called a leaf. Prove by (strong) mathematical induction that every rooted binary tree has exactly one more leaf nodes than nodes having two children. That is, if #0(T) is the number of leaves in binary tree T and #2(T) is the number of nodes in T having two children, then #0(T) = #2(T) + 1.

Hint: If T is a binary tree, it has one of the three forms illustrated below. One form corresponds to the base case. The other two depict the two cases that must be considered in the induction step.

In handling the "root has one child" case, you would consider the relationships among #0(T), #2(T), #0(TC), and #2(TC). Similarly, in handling the "root has two children" case, you would consider the relationships among #0(T), #2(T), #0(TL), #2(TL), #0(TR), and #2(TR).

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

5. Prove by (strong) mathematical induction that a rooted binary tree of height h contains at most 2h+1 − 1 nodes, for all h≥0.

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 "taller" subtree.

The remaining problems pertain to the Fibonacci sequence of numbers, defined as follows:

F0 = 0
F1 = 1
Fn =  Fn-1 + Fn-2   (for n>1)

6. Prove (by mathematical induction) that (+i | 0≤i≤n : Fi)  =  Fn+2 − 1 for all n≥0.

7. Prove (by mathematical induction) that (+i | 0≤i≤n : Fi2)  =  Fn × Fn+1 for all n≥0.