SUNY Geneseo Department of Computer Science

Introduction to Induction

{Date}

CSci 141, Spring 2005
Prof. Doug Baldwin

Misc

CSci learning center

Induction

A kind of reasoning that generalizes individual observations to universal rules

Base case - proves theorem for smallest numbers

Induction step - shows that if statement holds for smaller numbers, it must hold for larger numbers

Induction hypotheses - assuming theorem is true

Structure of induction proofs

Prove that the sum of the first n even integers is n(n+1), i.e.,

[Proof that Sum of First n Even Numbers is n(n+1)]

What does this have to do with computer science?

    sumUp( n )
        if n = 1
            return 2
        else
            return sumUp( n-1 ) + 2 * n

Postcondition: Result is n(n+1)
This is essentially the same calculation as described by the mathematical formula, but as a recursive algorithm it has very close connections to induction -- explicit use of "sumUp(n-1)" exactly as induction uses a hypothesis about a theorem applied to k-1, etc.
Induction is a very natural way to prove things about recursive algorithms.

Connection to Algorithms

A function f, defined on natural numbers:
- f(0) = 1
- f(n) = 1/f(n-1) + 2/f(n-1) if n > 0
f(0) = 1
f(1) = 1/1 + 2/1 = 3
f(2) = 1/3 + 2/3 = 1
f(3) = 3
Prove that f(n) = 1 or 3, no matter what n is
Examples above are base cases, rest of proof uses the fact that no matter what n is, if f(n-1) was 1 then f(n) will be 3, and vice versa -- this observation is basically the heart of an induction step, showing something about f at one value based on f at a smaller one, without concern for exactly what those values are.

Proofs about recursive algorithms

Read Section 7.1.2