Week 8: Strong Induction & Structural Induction

Question 1

template for writing mathematical induction proofs

Answer 1

• express statement to be proved “for all n >= b, P(n)” for b
• write “Basis Step”, then show P(b) is true
• write “Inductive Step”, state inductive hypothesis in form “assume P(k) is true for an arbitrary fixed int k >= b”
• write out what P(k+1) says
• prove the statement P(k+1) by assuming P(k) for all ints k with k >= b
• identify the conclusion of inductive step
• state conclusion by m.i, P(n) is true for all ints n >=b

Question 2

strong induction

Answer 2

• prove that P(n) is true for all positive
  integers n, complete two steps:
  1. BASIS STEP: Verify that P(1) is true.
  2. INDUCTIVE STEP: Show that
  [P(1) ∧ P(2) ∧∙∙∙ ∧ P(k)] → P(k + 1) is true for all positive
  integers k

Question 3

when we use strong induction

Answer 3

• used when we cannot easily prove a
  result using mathematical induction
• Strong induction and the principles of mathematical
  induction are equivalent

Question 4

recursively defined functions

Answer 4

A recursive or inductive definition of a function consists of two
parts.
* BASIS STEP: Specify the value of the function at zero.
* RECURSIVE STEP: A rule for finding the value of f(n) from preceding
function values

Question 5

examples of recursive definitions

Answer 5

1. 𝒇(𝒏) = 𝟐𝒏
   * 𝑓(0) = 1, 𝑓(𝑛 + 1) = 2 × 𝑓(𝑛)
2. 𝒇(𝒏) = 𝒏!
   * 𝑓(0) = 1, 𝑓(𝑛 + 1) = (𝑛 + 1) × 𝑓(𝑛)

Question 6

fibonacci numbers

Answer 6

Show that when n ≥ 3, fn > αn − 2, where α = (1 + √5)/2.
Solution: Let P(n) be the statement fn > αn−2 .
Use strong induction to show that P(n) is true when n ≥ 3.
BASIS STEP: P(3) holds since α < 2 = f3
P(4) holds since α2 = (3 + √5)/2 < 3 = f4
INDUCTIVE STEP:
Assume that P(j) holds; i.e., 𝑓𝑗 > αj−2 for all integers j with 3 ≤ j ≤ k,
where k ≥ 4.
Show that P(k + 1) holds, i.e., fk+1 > αk−1 .

Question 7

rooted trees

Answer 7

• A rooted tree consists of a set of vertices
  containing a distinguished vertex called the root, and edges
  connecting these vertices
• In data structures used to organize data and allow fast searching (or
  other queries)
• To represent relations (e.g., file structure, hierarchy in an
  organizations or systems, classify objects by properties

Question 8

recursive definition of rooted trees

Answer 8

• basis step: a single vertex r is a rooted tree
• recursive step: suppose that T1, T2, ..Tn are disjoint rooted trees with roots r1, r2,…rn respectively
• the rooted tree is formed by starting
  with a root r, which is not in any of the
  rooted trees T1, T2, …,Tn, and adding an
  edge from r to each of the roots r1,
  r2,…, rn.

Question 9

full binary trees

Answer 9

• BASIS STEP: A single vertex r is a full
  binary.
• RECURSIVE STEP: Assume T1 and T2
  are two disjoint full binary trees. Then, there is a full binary tree T
  consisting of
• a root r
• an edge connecting r to the root of
  the left subtree T1
• an edge connecting r to the root of
  the right subtree T2.
• Notation: T = T1∙T2

Question 10

building up full binary trees

Answer 10

• Full binary trees and their
  properties play a central
  role in data structures
  and algorithms.
• “Full“ refers to every
  vertex either being a
  leaf or having two
  subtrees

Question 11

structural induction

Answer 11

• To prove a property of the elements of a recursively defined
  set, we use structural induction.
• BASIS STEP: Show that the result holds for all elements specified in the
  basis step of the recursive definition.
• RECURSIVE STEP: Show that if the statement is true for each of the
  elements used to construct new elements in the recursive step of the
  definition, the result holds for these new elements.
• The validity of structural induction can be shown to follow from the
  principle of mathematical induction

Question 12

height or full binary trees

Answer 12

• The height h(T) of a full binary tree T is defined
  recursively:
  1. BASIS STEP:
• height h(T) = 0 if T consisting of only a root r
  2. RECURSIVE STEP:
• height h(T) = 1 + max {h(T1), h(T2)} if T = T1∙T2 andT1 and T2 are full binary trees

Question 13

number of vertices of full binary trees

Answer 13

1. BASIS STEP:
   * n(T) = 1 if T consisting of only a root r.
2. RECURSIVE STEP:
   * n(T) = 1 + n(T1) + n(T2) if T = T1∙T2 with T1 and T2 are full binary trees

Question 14

structural induction and binary trees

Answer 14

• Theorem: If T is a full binary tree, then n(T) ≤ 2h(T)+1 – 1.
• Proof: Use structural induction.
• BASIS STEP: The result holds for a full binary tree consisting of only the
  root: n(T) = 1 and h(T) = 0.
  Hence, n(T) = 1 ≤ 20+1 – 1 = - 1.RECURSIVE STEP:
• Let T1 be the tree rooted at the left child of root r and
• T2 be the tree rooted at the right child.
• As T1 and T2 are full binary trees,
  we have n(T1) ≤ 2h(T1)+1 – 1 and n(T2) ≤ 2h(T2)+1 – 1