Solution to Induction

WARNING: You should seriously try to answer this question before looking at the solution -- it's just a good study skill. Also, some answers on this page may be more brief than you would want to put down in an actual exam. If you want any type of partial credit, you should write more than just the solution.

P(u,v): (dot-product u v) = uv
Claim: For all lists, u and v, of the same length with only numbers, P(u,v) is true

Induction on the structure of u and v

Base Case: u and v are empty lists

(dot-product empty empty)

(if (and (empty? empty) (empty? empty))
    0
    (+ (* (head empty) (head empty))
       (dot-product (tail empty) (tail empty))))

0

Inductive Case:
Assume : (dot-product u v) = uv [Induction Hypothesis]
Prove : (dot-product (cons n₁ u) (cons n₂ v)) = [n₁,u][n₂,v]

(dot-product (cons n1 u) (cons n2 v))

(if (and (empty? (cons n1 u)) (empty? (cons n2 v)))
    0
    (+ (* (head (cons n1 u)) (head (cons n2 v)))
       (dot-product (tail (cons n1 u)) (tail (cons n2 v)))))

(+ (* n1 n2)
   (dot-product u v))

n1*n2 + uv [by IH]

[n1,u][n2,v]

Question

Return to CS 212 Prelim 1 - Spring 1999