SUNY Geneseo Department of Computer Science

Induction and Recursion

Previous Lecture

Questions?

0! = 1 because that's how mathematicians define it

• Because it turns out to be very convenient

Reading

Section 7.1.2

Induction proofs, how to use them to prove algorithms correct

• Basically the same as the math proofs, but fewer formulas
• Induction's base case is small problem, usually shows that algorithm's test chooses algorithm's base case, then algorithm base case works
• Induction step shows that test chooses recursive arm, which works assuming that recursive call works (induction hypothesis)

e.g., induction on actual values from method,

• Induction on boolean variable (walk-to-wall -- note: this wasn't truly induction on a boolean value, it was induction on the distance between a robot and a wall)

A bunch of different ways of using induction

Strong induction vs weak induction

Examples

How would you prove that our powerOf2 algorithm correctly computes 2ⁿ for any natural number n?

    int powerOf2( int n )
        if ( n > 0 )
            return 2 * powerOf2( n-1 )
        else
            return 1

• Base case: n = 0.
  • Trace algorithm on n = 0
  • 0 not > 0, algorithm does "else"
  • returns 1 = 2⁰
• Induction step:
  • Assume that "it works" for k-1 >= 0
    • Specifically, powerOf2(k-1) = 2^k-1
  • Show "it works" for k, specifically powerOf2(k) = 2^k
    • k > 0
    • Trace algorithm running with n = k
    • Algorithm passes test, returns 2 * powerOf2( k-1 )
    • = 2 * 2^k-1
    • = 2^k
      • [ 2 * 2^k-1 = 2¹ * 2^k-1 = 2^1+(k-1) = 2^k ]

Prove that this computes sum of the squares of the naturals between 0 and n

    sumSquares( n )
        if n > 0
            return n*n + sumSquare( n-1 )
        else
            return 0

• Base case. n = 0
  • Trace algorithm
  • n not greater than 0
  • Returns 0 = 0² = sum of sqaures from 0 to 0
• Induction step:
  • Assume "it works" for k-1 >= 0
    • i.e., sumSquares( k-1 ) returns the sum of the squares of the naturals between 0 and k-1
  • Trace algorithm for k (show "it works" for k)
    • k > 0
    • Returns (k)*(k) + sumSquares(k-1)
    • = k² + sum of squares from 0 to k-1
    • = sum of squares from 0 to k

Prove that this algorithm determines whether natural number n is odd or even:

    isOdd( n )
        if ( n == 0 )
            return false
        else if ( n == 1 )
            return true
        else 
            return isOdd( n - 2 )

• Try this as a mini-assignment for Monday

Next Lecture