Welcome To Sora Park

Before diving into proving that a recursive algorithm is correct, the following page is recommended to read through in order to understand what the recursive algorithm is and how it works:

2021.08.25 - [Algorithms] - Recursive Algorithm 재귀 알고리즘

Mathematical induction, and its variant strong induction, can be used to prove the correctness of a recursive algorithm.

# Example 1: powers of real numbers

Method: mathematical induction

• Basis step:
  If n = 0, the first step of the algorithm is that power(a, 0) = 1. This is correct because a^0 = 1 for every nonzero real number a.
• Inductive step:
  The inductive hypothesis is the statement that power(a, k) = a^k for all a ≠ 0 for an arbitrary nonnegative integer k. That is, the inductive hypothesis is the statement that the algorithm correctly computes a^k. If the inductive hypothesis is true, the algorithm correctly computes a^(k+1).
  
  Because k+1 is a positive integer, when the algorithm computes a^(k+1), the algorithm sets power(a, k+1) = a * power(a, k). By the inductive hypothesis,
  - power(a, k) = a^k, so
  - a * power(a, k) = a * a^k = a^(k+1)
  This completes the inductive step!

Hence, the algorithm always computes a^n correctly when a ≠ 0 and n is a non-negative integer.

# Example 2: modular powers

Method: strong induction

• Basis step:
  Let b be an integer and m an integer with m ≥ 2.
  When n = 0, the algorithm sets mpower(b, n, m) equal to 1 (m ≥ 2). This is correct because b^0 mod m = 1.
• Inductive step:
  The inductive hypothesis is the statement that mpower(b, j, m) = b^j mod m for all integers 0 ≤ j < k whenever b is a positive integer and m is an integer with m ≥ 2. If the inductive hypothesis is correct, mpower(b, k, m) = b^k mod m.
  
  Because the recursive algorithm handles odd and even values of k differently, the inductive step should be split into two cases:
  - When k is even, mpower(b, k, m) =
  (mpower(b, k/2, m))^2 mod m =
  (b^(k/2) mod m)^2 mod m = 
  b^k mod m
  where the inductive hypothesis was used to replace mpower(b, k/2, m) = b^k mod m.
  - When k is odd, mpower(b, k, m) =
  (((mpower(b, floor(k/2), m))^2 mod m * b mod m) mod m =
  (((b^(floor(k/2)) mod m)^2 mod m * b mod m) mod m = 
  b^(2 * floor(k/2) + 1) mod m =
  b^k mod m
  because 2 * floor(k/2) + 1 = 2 * (k-1) / 2 + 1 = k when k is odd.
  The inductive hypothesis was used to replace mpower(b, floor(k/2), m) by b^(floor(k/2)) mod m.

Both steps have been completed by strong induction, so this algorithm is correct! 

Generally, to prove that recursive algorithms are correct, strong induction is more often used rather than just mathematical induction.